【NOIP2006】作業調度方案 {語文難題}

Description:

　　我們現在要利用 m 台機器加工 n 個工件，每個工件都有 m 道工序，每道工序都在不同的指定的機器上完成。每個工件的每道工序都有指定的加工時間。 
　　每個工件的每個工序稱為一個操作，我們用記號 j-k 表示一個操作，其中 j 為 1 到 n 中的某個數字，為工件號； k 為 1 到 m 中的某個數字，為工序號，例如 2-4 表示第 2 個工件第 4 道工序的這個操作。在本題中，我們還給定對於各操作的一個安排順序。 
　　例如，當 n=3 ， m=2 時，“ 1-1 ， 1-2 ， 2-1 ， 3-1 ， 3-2 ， 2 -2 ” 就是一個給定的安排順序，即先安排第 1 個工件的第 1 個工序，再安排第 1 個工件的第 2 個工序，然後再安排第 2 個工件的第 1 個工序，等等。 
　　一方面，每個操作的安排都要滿足以下的兩個約束條件。 
　　(1) 對同一個工件，每道工序必須在它前面的工序完成後才能開始； 
　　(2) 同一時刻每一臺機器至多只能加工一個工件。 
　　另一方面，在安排後面的操作時，不能改動前面已安排的操作的工作狀態。 
　　由於同一工件都是按工序的順序安排的，因此，只按原順序給出工件號，仍可得到同樣的安排順序，於是，在輸入數據中，我們將這個安排順序簡寫為“ 1 1 2 3 3 2 ” 。 
　　還要註意，“安排順序”只要求按照給定的順序安排每個操作。不一定是各機器上的實際操作順序。在具體實施時，有可能排在後面的某個操作比前面的某個操作先完成。 
　　例如，取 n=3,m=2 ，已知數據如下：

　　當一個操作插入到某台機器的某個空檔時（機器上最後的尚未安排操作的部分也可以看作一個空檔），可以靠前插入，也可以靠後或居中插入。為了使問題簡單一些， 我們約定：在保證約束條件（ 1 ）（ 2 ）的條件下，儘量靠前插入。並且，我們還約定，如果有多個空檔可以插入，就在保證約束條件（ 1 ）（ 2 ）的條件下，插入到最前面的一個空檔。於是，在這些約定下，上例中的方案一是正確的，而方案二是不正確的。 
　　顯然，在這些約定下，對於給定的安排順序，符合該安排順序的實施方案是唯一的，請你計算出該方案完成全部任務所需的總時間。

solution:

　　這道題完全是在考語文水平啊,數據範圍都異常的小!然而我還是被坑了!

　　首先是題目描述本來就模模糊糊的,這道題是說按照順序一個一個的去考慮他所給出的順序的工件,按照要求放入隊列,但是放入隊列的時候要註意很多

　　例如:

• 1,2,3,4號工件先後放入,都是放入第一臺機器.
• 然後再放入4,放入第二台機器.

• 假設第一臺機器已經占用了時間20s,那麼第二台機器的4號工件必須從20s開始(同一個工件要按照工序去生產).
• 那麼1~20s就是空餘的.
• 如果再插入一個1號工件在2號機器,那麼就要插到4號前面去了,即使與它給的順序不同.

codes:

 1 #include<queue>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<cstring>
 5 #include<iostream>
 6 #include<algorithm>
 7 #define RG register
 8 using namespace std;
 9 int n,m,top,ans;
10 int Time[23][23],mach[23][23],tot[23];
11 int que[500],Rank[500],Lasttime[23];
12 bool work[23][500];
13 bool check(int Begin,int T,int id)
14 {
15   for(int i=Begin;i<Begin+T;i++)
16     if(work[id][i])
17       return 0;
18   return 1;
19 }
20 int main()
21 {
22   scanf("%d%d",&m,&n);
23   top=n*m;
24   for(int i=1;i<=top;i++)
25     {
26       scanf("%d",&que[i]);
27       tot[que[i]]++;
28       Rank[i]=tot[que[i]];
29     }
30   for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&mach[i][j]);
31   for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&Time[i][j]);
32   for(int j=1,i;j<=top;j++)
33     {
34       int now=que[j];//當前的工件號
35       int id=mach[now][Rank[j]];//當前的工序的機器號
36       for(i=Lasttime[now]+1;;i++)
37     {
38       if(!work[id][i])//檢查是否可以插入任務
39         if(check(i,Time[now][Rank[j]],id))break;
40     }
41       int End=i+Time[now][Rank[j]]-1;
42       for(i;i<=End;i++)work[id][i]=1;
43       Lasttime[now]=End;
44       ans=max(ans,End);
45     }
46   cout<<ans<<endl;
47   return 0;
48 }