描述

一家工廠的流水線正在生產一種產品，這需要兩種操作：操作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

總結

以上是生活随笔為你收集整理的Job Processing 工序安排的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。