程序填空题：求解流水作业调度问题（贪心法）

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

```c++
#include
#include
#include
using namespace std;
#define N 100
//问题表示
int n;
int a[N]; //对应M1的时间
int b[N]; //对应M2的时间
struct NodeType
{
int no; //作业序号
bool group; //1代表第一组N1,0代表第二组N2
int time; //a,b的最小时间
bool operator<(const NodeType &s) const
{
return time }
};
int best[N]; //最优调度序列

int solve() //求解流水作业调度问题
{
int i,j,k;
NodeType c[N];
for(i=0;i {
c[i].no=i;
c[i].group=(a[i]<=b[i]); //a[i]<=b[i]对应第1组N1,a[i]>b[i]对应第0组N2
c[i].time=a[i]<=b[i]?a[i]:b[i]; //第1组存放a[i],第0组存放b[i]
}
sort(c,c+n); //c元素按time递增排序
j=0; k=n-1;
for(i=0;i {
if(c[i].group==1) //第1组,按time递增排列放在best的前面部分
;
else //第0组,按time递减排列放到best的后面部分
;
}
int f1=0; //累计M1上的执行时间
int f2=0; //最优调度下的消耗总时间
for(i=0;i {
f1+=a[best[i]];
f2=;
}
;
}

int main()
{
cin>>n;
for(int i=0;i cin>>a[i]>>b[i];
printf("%d\n",solve());
return 0;
}
```

### 输入格式:

第一行输入作业数n，接着的n行分别为在M1和M2加工各作业所需的时间。

### 输出格式:
输出所需加工时间

### 输入样例1:

```in
4
5 6
12 2
4 14
8 7
```

### 输出样例1:

```out
33
```





答案：
第1空：best[j++]=c[i].no

第2空： best[k--]=c[i].no

第3空：max(f2,f1)+b[best[i]]

第4空：return f2