我們現在要利用 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
|
1/3
|
2/2
|
2
|
1/2
|
2/5
|
3
|
2/2
|
1/4
|
則對於安排順序“ 1 1 2 3 3 2 ” ，下圖中的 兩個實施方案都是正確的。但所需要的總時間分別是 10 與 12 。
當 一個操作插入到某臺機器的某個空檔時（機器上最後的尚未安排操作的部分也可以看作一個空檔），可以靠前插入，也可以靠後或居中插入。爲了使問題簡單一些， 我們約定：在保證約束條件（ 1 ）（ 2 ）的條件下，儘量靠前插入。並且，我們還約定，如果有多個空檔可以插入，就在保證約束條件（ 1 ）（ 2 ）的條件下，插入到最前面的一個空檔。於是，在這些約定下，上例中的方案一是正確的，而方案二是不正確的。
顯然，在這些約定下，對於給定的安排順序，符合該安排順序的實施方案是唯一的，請你計算出該方案完成全部任務所需的總時間。
【輸入文件】
輸入文件 jsp.in 的第 1 行爲兩個正整數，用一個空格隔開：m n
（其中 m （ <20 ）表示機器數， n （ <20 ）表示工件數）
第 2 行： 個用空格隔開的數，爲給定的安排順序。
接下來的 2n 行，每行都是用空格隔開的 m 個正整數，每個數不超過 20 。
其中前 n 行依次表示每個工件的每個工序所使用的機器號，第 1 個數爲第 1 個工序的機器號，第 2 個數爲第 2 個工序機器號，等等。
後 n 行依次表示每個工件的每個工序的加工時間。
可以保證，以上各數據都是正確的，不必檢驗。
【輸出文件】
輸出文件 jsp.out 只有 一個正整數，爲最少的加工時間。
【輸入輸出樣例】
jsp.in
2 3
1 1 2 3 3 2
1 2
1 2
2 1
3 2
2 5
2 4
jsp.out
10
【分析】
作為NOIP2006的第三題，題目又這麼長，真是很考驗人的耐心～
不過如果把題讀懂了，發現該題十分簡單。
一下題解來自BYVoid大牛的博客：
http://www.byvoid.com/blog/noip-allsolutions/做這道題關鍵在於理解題意。這道題讓我想起了流水作業調度的Johnson算法，雖然與這道題無關。
提示幾點
1、每個工件的每個工序對應着不同的機器。
2、一個工件必須按照加工順序加工。
3、把每個機器看成一個時間軸，每個時間對應着加工一個工件，或者爲空閒狀態。
4、題中的算法是給定的貪心策略，不需要構造，只要模擬。
由於數據很小，把每個機器的時間軸用布爾數組表示，true爲該時間有工件在加工，false爲空閒。
按照給定的順序，一件一件得往時間軸上插入，每個工件插入的位置必須在前面的工序都完成以後的時間斷插入。每次插入掃描一遍時間軸數組，找到最前面一個。
其實題中所給的圖已經一目瞭然了。理解題意以後，會發現這是NOIP2006最簡單的題。
【我的代碼】
//NOIP2006-jsp
#include <fstream>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
ifstream fin("jsp.in");
ofstream fout("jsp.out");
const int MT=1000;
const int MAX=21;
int M,N;//M:機器數,N:工件數
int S[MAX*MAX];
class JSP
{
public:
int Mach[MAX];
int Time[MAX];
int Start;
int Todo;
JSP()
{
for (int i=1;i<=MAX;i++)
{
Mach[i]=0;
Time[i]=0;
}
Start=0;
Todo=1;
}
}P[MAX];
class Machine
{
public:
bool Use[1001];//true:被佔用,false:空閒.
Machine()
{
for(int i=0;i<=MT;i++)
Use[i]=false;
}
}U[MAX];
void init()
{
fin>>M>>N;
int i,j;
for (i=1;i<=M*N;i++)
fin>>S[i];
for (i=1;i<=N;i++)
for (j=1;j<=M;j++)
fin>>P[i].Mach[j];
for (i=1;i<=N;i++)
for (j=1;j<=M;j++)
fin>>P[i].Time[j];
return;
}
void Tanxin()
{
int i,j,k;//臨時變量
int c;//當前工件
int t;//當前工序的耗時
int m;//當前工序的機器
bool brin;//是否可以在當前時間插入機器
for(i=1;i<=M*N;i++)
{
c=S[i];
m=P[c].Mach[P[c].Todo];
t=P[c].Time[P[c].Todo];
for (j=P[c].Start;j<=MT;j++)
{
brin=true;
for (k=j;k<=j+t-1;k++)
{
if(U[m].Use[k])
{
brin=false;
break;
}
}
if (brin)
{
for (k=j;k<=j+t-1;k++)
U[m].Use[k]=true;
P[c].Start=j+t;
P[c].Todo++;
break;
}
}
}
return;
}
int main()
{
int maxn=0;
init();
Tanxin();
for (int i=1;i<=M;i++)
{
for (int j=MT-1;j>=0;j--)
{
if (U[i].Use[j])
{
if (j>maxn)
maxn=j;
break;
}
}
}
fout<<++maxn<<endl;
return 0;
}
正在连接评测机...#include <fstream>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
ifstream fin("jsp.in");
ofstream fout("jsp.out");
const int MT=1000;
const int MAX=21;
int M,N;//M:機器數,N:工件數
int S[MAX*MAX];
class JSP
{
public:
int Mach[MAX];
int Time[MAX];
int Start;
int Todo;
JSP()
{
for (int i=1;i<=MAX;i++)
{
Mach[i]=0;
Time[i]=0;
}
Start=0;
Todo=1;
}
}P[MAX];
class Machine
{
public:
bool Use[1001];//true:被佔用,false:空閒.
Machine()
{
for(int i=0;i<=MT;i++)
Use[i]=false;
}
}U[MAX];
void init()
{
fin>>M>>N;
int i,j;
for (i=1;i<=M*N;i++)
fin>>S[i];
for (i=1;i<=N;i++)
for (j=1;j<=M;j++)
fin>>P[i].Mach[j];
for (i=1;i<=N;i++)
for (j=1;j<=M;j++)
fin>>P[i].Time[j];
return;
}
void Tanxin()
{
int i,j,k;//臨時變量
int c;//當前工件
int t;//當前工序的耗時
int m;//當前工序的機器
bool brin;//是否可以在當前時間插入機器
for(i=1;i<=M*N;i++)
{
c=S[i];
m=P[c].Mach[P[c].Todo];
t=P[c].Time[P[c].Todo];
for (j=P[c].Start;j<=MT;j++)
{
brin=true;
for (k=j;k<=j+t-1;k++)
{
if(U[m].Use[k])
{
brin=false;
break;
}
}
if (brin)
{
for (k=j;k<=j+t-1;k++)
U[m].Use[k]=true;
P[c].Start=j+t;
P[c].Todo++;
break;
}
}
}
return;
}
int main()
{
int maxn=0;
init();
Tanxin();
for (int i=1;i<=M;i++)
{
for (int j=MT-1;j>=0;j--)
{
if (U[i].Use[j])
{
if (j>maxn)
maxn=j;
break;
}
}
}
fout<<++maxn<<endl;
return 0;
}
已连接到评测机
| GRID | 1 |
| 名称 | Flitty |
| 系统版本 | 1.00 |
| 备注 | COGS 1号评测机 Flitty |
编译成功
| 测试点 | 结果 | 得分 | 运行时间 | 内存使用 | 退出代码 |
| 1 | 正确 | 10 | 0.015 s | 301 KB | 0 |
| 2 | 正确 | 10 | 0.001 s | 301 KB | 0 |
| 3 | 正确 | 10 | 0.000 s | 301 KB | 0 |
| 4 | 正确 | 10 | 0.001 s | 301 KB | 0 |
| 5 | 正确 | 10 | 0.001 s | 301 KB | 0 |
| 6 | 正确 | 10 | 0.001 s | 301 KB | 0 |
| 7 | 正确 | 10 | 0.001 s | 301 KB | 0 |
| 8 | 正确 | 10 | 0.001 s | 301 KB | 0 |
| 9 | 正确 | 10 | 0.001 s | 301 KB | 0 |
| 10 | 正确 | 10 | 0.001 s | 301 KB | 0 |
运行时间 0.020 s
平均内存使用 301 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!
沒有留言:
張貼留言