51nod 1205 流水线调度

阅读量：7226 次

发布时间：2019-06-29

本文共 1685 字，大约阅读时间需要 5 分钟。

基准时间限制：1 秒空间限制：131072 KB 分值: 40

关注

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示例

43 72 11 14 2

Output示例

题解：

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

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

　　sort一下。

　　第一个集合的作业顺序：在S1上的时间不递减（小的在前面）

　　第二个集合的作业顺序：在S2上的时间不递增（大的在前面）

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              10 #include 
               
                11 #include 
                
                 12 using namespace std;13 typedef long long LL;14 #define ms(a, b) memset(a, b, sizeof(a))15 #define pb push_back16 #define mp make_pair17 const LL INF = 0x7fffffff;18 const int inf = 0x3f3f3f3f;19 const int mod = 1e9+7;20 const int maxn = 50000+10;21 struct task22 {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
                 
                  > a >> b;43 if(a
                  
                   < ans ? ans+Task1[i].t2 : sum+ Task1[i].t2;68 }69 cout << ans << endl;70 }71 int main() {72 #ifdef LOCAL73 freopen("input.txt", "r", stdin);74 // freopen("output.txt", "w", stdout);75 #endif76 init();77 solve();78 return 0;79 }

View Code

转载于:https://www.cnblogs.com/denghaiquan/p/7219926.html

你可能感兴趣的文章