网站后期维护价格,榜单设计,网站界面设计方案,linux系统问题描述 有 n 个作业#xff08;编号为1#xff5e;n#xff09;要在由两台机器 M 1和 M 2 组成的流水线上完成加工。每个作业加工的顺序都是先在 M 1上加工#xff0c;然后在 M 2 上加工。 M 1 和 M 2 加工作业 i 所需的时间分别为 a i 和 b i#xff08;1≤i≤n编号为1n要在由两台机器 M 1和 M 2 组成的流水线上完成加工。每个作业加工的顺序都是先在 M 1上加工然后在 M 2 上加工。 M 1 和 M 2 加工作业 i 所需的时间分别为 a i 和 b i1≤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
注意算法的时间复杂度优化避免评测超时。
补充代码 #includebits/stdc.husing 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 i1;in;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,f20;int l 1,rn;for(int i1;in;i){if(Nodes[i].t a[Nodes[i].idx]){ans[l] Nodes[i].idx;}else{ans[r --] Nodes[i].idx;}}for(int i1;in;i){int id ans[i];f1 a[id];f2 max(f1,f2) b[id];}cout f2 endl;}int main () {solve();return 0;}
