Job Processing 工序安排

描述

一家工厂的流水线正在生产一种产品，这需要两种操作：操作A和操作B。每个操作只有一些机器能够完成。

上图显示了按照下述方式工作的流水线的组织形式。A型机器从输入库接受工件，对其施加操作A，得到的中间产品存放在缓冲库。B型机器从缓冲库接受中间产品，对其施加操作B，得到的最终产品存放在输出库。所有的机器平行并且独立地工作，每个库的容量没有限制。每台机器的工作效率可能不同，一台机器完成一次操作需要一定的时间。

给出每台机器完成一次操作的时间，计算完成A操作的时间总和的最小值，和完成B操作的时间总和的最小值。

格式

PROGRAM NAME: job

INPUT FORMAT:

(file job.in)

第一行 三个用空格分开的整数：N，工件数量 (1<=N<=1000);M1，A型机器的数量 (1<=M1<=30);M2，B型机器的数量 (1<=M2<=30)。

第二行…等 M1个整数（表示A型机器完成一次操作的时间，1..20），接着是M2个整数（B型机器完成一次操作的时间，1..20）

OUTPUT FORMAT:

(file job.out)

只有一行。输出两个整数：完成所有A操作的时间总和的最小值，和完成所有B操作的时间总和的最小值（A操作必须在B操作之前完成）。

SAMPLE INPUT

5 2 3
1 1 3 1 4

SAMPLE OUTPUT

3 5题解：很纠结啊，这道题。百度了好多题解，最终都指向这个网站：http://magicalcode.blogbus.com/logs/37193487.html处理A操作很简单，用贪心法就可以。关键是如何求B操作所用时间。我们可以把B操作倒过来，比如操作序列是：AWWWWB(注:A代表A操作，W代表等待，B代表B操作)，我们A操作后，在倒过来B操作。

每个工件在B机器做都有自己的最短时间，但是它比A多了一个时间，就是这个工件的抵达时间，就是说要从B出来的时间应该是两者的和，这样的话，如果两两相加，就覆盖了所有可能的情况，最后只需要在这个里面找一个最大的即可。这里的最大是指整体的时间都是最小的时候里面的一个最大的。

代码：

1 /*
 2  ID:10239512
 3  PROG:job
 4  LANG:C++    
 5     */ 
 6 
 7 //#include <iostream> 
 8 #include<fstream>
 9 #include<cstring> 
10 using namespace std;
11 ifstream cin("job.in");
12 ofstream cout("job.out");
13 
14 int n,ma,mb,ta[31],tb[31],a[31],b[31],fa[1001],fb[1001]; 
15 
16 void Quick(int left,int right,int p){
17      if(left>=right) return ; 
18      int l=left,r=right; 
19      if(p==0)
20      {
21       int mid=fa[(left+right)/2];
22       while(l<=r)
23       {
24        while(fa[l]>mid) l++;
25        while(fa[r]<mid) r--;
26        if(l<=r) {swap(fa[l],fa[r]);l++;r--;} 
27                  } 
28              } 
29      
30      if(p==1)
31      {
32       int mid=fb[(left+right)/2];
33       while(l<=r)
34       {
35        while(fb[l]<mid) l++;
36        while(fb[r]>mid) r--;
37        if(l<=r) {swap(fb[l],fb[r]);l++;r--;} 
38                  } 
39              } 
40      Quick(left,r,p);
41      Quick(l,right,p); 
42      } 
43 
44 int main()
45 {
46     cin>>n>>ma>>mb;
47     for(int i=1;i<=ma;++i)
48     cin>>ta[i];
49     for(int i=1;i<=mb;++i)
50     cin>>tb[i];
51     
52     for(int i=1;i<=n;++i)
53     {
54      int mi=1;
55      for(int j=2;j<=ma;++j)
56      if(a[j]+ta[j]<a[mi]+ta[mi])
57      mi=j;
58      a[mi]+=ta[mi]; 
59      fa[i]=a[mi];
60      mi=1; 
61      for(int j=2;j<=mb;++j)
62      if(b[j]+tb[j]<b[mi]+tb[mi])
63      mi=j;
64      b[mi]+=tb[mi];
65      fb[i]=b[mi]; 
66             } 
67     
68     Quick(1,n,0);
69     Quick(1,n,1); 
70     
71     cout<<fa[1]<<" ";
72     
73     int mi=1;
74     for(int i=2;i<=n;++i)
75     if(fa[i]+fb[i]>fa[mi]+fb[mi])
76     mi=i; 
77 
78     cout<<fa[mi]+fb[mi]<<endl;
79     return 0; 
80 
81     }

原文链接: https://www.cnblogs.com/noip/archive/2012/06/01/2530772.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍