首页 > 代码库 > 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 }
51nod 1205 流水线调度
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。