2015年6月29日 星期一

[CF 452D] Washer, Dryer, Folder

作法:

一開始每台機器可以運行的時間都是$0$,因此第一件衣服可以馬上丟進去。再來依次處理每件衣服,找出他最早可以丟進去的時間並放進去。至於如何找最早的時間,我們對三台機器都維護一個 priority_queue ,裡面分別存每台機器要到時間多少時才有空,那麼每次從中取出最小的三個時間就可以算出下一次的衣服要在什麼時候放進去了。並且也可以計算出處理這件衣服的機器分別會在什麼時候結束工作。

code :



#include<bits/stdc++.h>
using namespace std;
 
priority_queue<int,vector<int>,greater<int> > pq1,pq2,pq3 ;
main()
{
    int k,n1,n2,n3,t1,t2,t3 ;
    scanf("%d%d%d%d%d%d%d",&k,&n1,&n2,&n3,&t1,&t2,&t3) ;
    while(n1--) pq1.push(0) ;
    while(n2--) pq2.push(t1) ;
    while(n3--) pq3.push(t1+t2) ;
    while(k--)
    {
        int x=pq1.top() ; pq1.pop() ;
        int y=pq2.top() ; pq2.pop() ;
        int z=pq3.top() ; pq3.pop() ;
        int t=max(max(x,y-t1),z-t1-t2) ;
        pq1.push(t+t1) ;
        pq2.push(t+t1+t2) ;
        pq3.push(t+t1+t2+t3) ;
        if(!k) printf("%d\n",t+t1+t2+t3) ;
    }
}
 

沒有留言:

張貼留言