问题就是2台机器，n件任务，必须先在S1上做，再在S2上做。任务之间先做后做任意。求最早的完工时间。
这是一个经典问题：2台机器的情况下有多项式算法（Johnson算法），3台或以上的机器是NP-hard的。思想就是贪心，时间复杂度是O(nlogn) 。
Johnson算法
(1) 把作业按工序加工时间分成两个子集，第一个集合中在S1上做的时间比在S2上少，其它的作业放到第二个集合。先完成第一个集合里面的作业，再完成第二个集合里的作业。
(2) 对于第一个集合，其中的作业顺序是按在S1上的时间的不减排列；对于第二个集合，其中的作业顺序是按在S2上的时间的不增排列。
怎么证呢？
1: #include <iostream>
2: #include <cstdio>
3: #include <algorithm>
4: using namespace std;
5: const int maxn = 10005;
6: struct node{
7: int x,y;
8: }a[maxn],b[maxn],c[maxn];
9: bool cmp1(const node &p, const node &q)
10: {
11: return p.x < q.x;
12: }
13: bool cmp2(const node &p, const node &q)
14: {
15: return p.y > q.y;
16: }
17: int n;
18: int s1sum[maxn];
19: int sum;
20: int main()
21: {
22: //freopen("test.txt","r",stdin);
23: while(scanf("%d",&n) && n)
24: {
25: for(int i=0;i<n;++i)
26: scanf("%d%d",&a[i].x,&a[i].y);
27: int len1 = 0, len2 = 0;
28: for(int i=0;i<n;++i)
29: {
30: if(a[i].x < a[i].y)
31: {
32: b[len1].x = a[i].x; //子集1 x<y
33: b[len1++].y = a[i].y;
34: }
35: else
36: {
37: c[len2].x = a[i].x; //子集2
38: c[len2++].y = a[i].y;
39: }
40: }
41: sort(b,b+len1,cmp1); //子集1作业顺序：x不减
42: sort(c,c+len2,cmp2); //子集2作业顺序：y不增
43: for(int i = len1;i<len1+len2;++i)
44: b[i] = c[i-len1];
45: s1sum[0] = 0;
46: for(int i=0;i<n;++i)
47: s1sum[i+1] = s1sum[i]+b[i].x;
48: sum = 0;
49: for(int i=0;i<n;++i)
50: {
51: if(sum<s1sum[i+1]) sum = s1sum[i+1]+b[i].y;
52: else sum+=b[i].y;
53: }
54: printf("%d\n",sum);
55: }
56: }
原文链接：https://www.qiquanji.com/post/8454.html
本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。
微信扫码关注
更新实时通知