头歌实训作业 算法设计与分析-贪心算法(第5关：求解流水作业调度问题)

问题描述

有 n 个作业（编号为1～n）要在由两台机器 M 1和 M 2 组成的流水线上完成加工。每个作业加工的顺序都是先在 M 1​上加工，然后在 M 2  上加工。 M 1 和 M 2  加工作业 i 所需的时间分别为 a i 和 b i（1≤i≤n）。
流水作业调度问题要求确定这 n 个作业的最优加工顺序，使得从第一个作业在机器 M 1 上开始加工，到最后一个作业在机器 M 2 上加工完成所需的时间最少。可以假定任何作业一旦开始加工，就不允许被中断，直到该作业被完成，即非优先调度。

测试说明

输入格式:
第一行输入作业数 n，接着的 n 行分别为在 M 1和M 2 加工各作业所需的时间。

输出格式:
输出最优调度方案（时间最少）所需的时间。

输入样例1:
4
5 6  作业1在M1上执行时间为5，在M2上执行时间为6
12 2
4 14
8 7

输出样例1：
33

输出样例1解释：
总时间=33
调度方案
第1步执行作业3
第2步执行作业1
第3步执行作业4
第4步执行作业2

注意算法的时间复杂度优化，避免评测超时。

补充代码： 

 #include<bits/stdc++.h>
 using namespace std;
 typedef long long ll;
 const int N =1010;
 struct Node{
     ll t, idx;
 }Nodes[N];

 int a[N],b[N];
 bool cmp(Node & a , Node & b){
     return a.t< b.t;
 }
 int ans[N];

 void solve(){
     int n;
     cin >> n;
     for(int i=1;i<=n;i++){
         Nodes[i].idx = i;
         cin >> a[i] >> b[i];
         if(a[i] <= b[i]){
             Nodes[i].t = a[i];
         }
         else{
             Nodes[i].t = b[i];
         }
     }

         sort(Nodes + 1, Nodes +1 +n,cmp);
         int f1 =0,f2=0;
         int l =1,r=n;
         for(int i=1;i<=n;i++){
             if(Nodes[i].t == a[Nodes[i].idx]){
                 ans[l++] = Nodes[i].idx;
             }
             else{
                 ans[r --] = Nodes[i].idx;
             }
         }

         for(int i=1;i<=n;i++){
             int id = ans[i];
             f1 += a[id];
             f2 = max(f1,f2) + b[id];
         }
         cout << f2 << endl;
    
 }
 int main () {
     solve();
     return 0;
 }