首页 > 代码库 > 51nod 1205 流水线调度

51nod 1205 流水线调度

1205 流水线调度技术分享
基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题
技术分享 收藏
技术分享 关注
N个作业{1,2,…,n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工,然后在M2上加工。M1和M2加工作业i所需的时间分别为a[i]和b[i]。你可以安排每个作业的执行顺序,使得从第一个作业在机器M1上开始加工,到最后一个作业在机器M2上加工完成所需的时间最少。求这个最少的时间。
 
Input
第1行:1个数N,表示作业的数量。(2 <= N <= 50000)
第2 - N + 1行:每行两个数,中间用空格分隔,表示在M1和M2上加工所需的时间a[i], b[i]。(1 <= a[i], b[i] <= 10000)。
Output
输出完成所有作业所需的最少时间。
Input示例
4
3 7
2 1
1 1
4 2
Output示例
14

 

 

题解:

  流水线调度的经典问题,2台机器的情况下用Johnson算法, 3台或以上机器用 NP-hard 算法。

 

  简单讲一下,就是把任务分成2个集合。当s1的时间小于s2的时间放到第一个集合,其他的放到第二个集合。

  sort一下。

  第一个集合的作业顺序:在S1上的时间不递减(小的在前面)

  第二个集合的作业顺序:在S2上的时间不递增(大的在前面)

  

  

技术分享
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 #include <algorithm>
 6 #include <cmath>
 7 #include <vector>
 8 #include <queue>
 9 #include <map>
10 #include <stack>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 #define ms(a, b) memset(a, b, sizeof(a))
15 #define pb push_back
16 #define mp make_pair
17 const LL INF = 0x7fffffff;
18 const int inf = 0x3f3f3f3f;
19 const int mod = 1e9+7;
20 const int maxn = 50000+10;
21 struct task
22 {
23     int t1, t2;
24 }Task1[maxn], Task2[maxn];
25 int cnt1, cnt2;
26 bool cmp1(task x1, task x2)
27 {
28     return x1.t1 <= x2.t1;
29 }
30 bool cmp2(task x1, task x2)
31 {
32     return x1.t2 >= x2.t2;
33 }
34 void init() {
35     cnt1 = cnt2 = 0;
36 }
37 void solve() {
38     int n;
39     cin >> n;
40     for(int i = 0;i<n;i++){
41         int a, b;
42         cin >> a >> b;
43         if(a<b){
44             Task1[cnt1].t1 = a;
45             Task1[cnt1++].t2 = b;
46         }
47         else{
48             Task2[cnt2].t1 = a;
49             Task2[cnt2++].t2 = b;
50         }
51     }
52     sort(Task1, Task1+cnt1, cmp1);
53     sort(Task2, Task2+cnt2, cmp2);
54 
55     for(int i = 0;i<cnt2;i++)
56         Task1[cnt1++] = Task2[i];
57 
58 //    for(int i = 0;i<n;i++){
59 //        cout << Task1[i].t1 << " " << Task1[i].t2 << endl;
60 //    }
61 
62     int ans = Task1[0].t1 + Task1[0].t2;
63     int sum = Task1[0].t1;
64 
65     for(int i = 1;i<cnt1;i++){
66         sum += Task1[i].t1;
67         ans = sum < ans ? ans+Task1[i].t2 : sum+ Task1[i].t2;
68     }
69     cout << ans << endl;
70 }
71 int main() {
72 #ifdef LOCAL
73     freopen("input.txt", "r", stdin);
74 //        freopen("output.txt", "w", stdout);
75 #endif
76     init();
77     solve();
78     return 0;
79 }
View Code

 

51nod 1205 流水线调度