深圳深圳网站制作站长网站工具

问题描述

有 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;}