MemSQL start[c]up 2.0 Round 1 : D. Washer, Dryer, Folder

Cよりもあっさり解けた。
http://codeforces.com/contest/452/problem/D

問題

K個の洗濯物があるので、それぞれ洗濯機→脱水機→折りたたみ機に掛けていきたい。
各機械はN[i]台あり、それぞれかかる時間はT[i]ある。
１つの機械は同時に１つの洗濯物しか処理できない。

また、各洗濯物は洗濯機→脱水機→折りたたみ機の３過程は時間に隙間なく行わなければならない。
K個の洗濯物の処理を終える最短時間を答えよ。

解法

priority_queueを用いて、洗濯機・脱水機・折りたたみ機のうちそれぞれ最初に使えるようになる時刻をP[0]、P[1]、P[2]とし、洗濯物の数だけ洗濯機に掛け始める最初の時間を求めていく。

洗濯機に掛ける時間yはmin(P[0],P[1]-T[0],P[2]-T[0]-T[1])となる。
その後、各priority_queueに各機械が次に使えるようになる時刻としてy+T[0]、y+T[0]+T[1]、y+T[0]+T[1]+T[2]を追加していけばよい。

K回priority_queueを処理するのでO(K*logN)で処理可能。

int K,N[3],T[3];
priority_queue<int,vector<int>,greater<int> > A[3];

void solve() {
	int f,i,j,k,l,x,y;
	cin>>K>>N[0]>>N[1]>>N[2]>>T[0]>>T[1]>>T[2];
	
	FOR(i,N[0]) A[0].push(0);
	FOR(i,N[1]) A[1].push(0);
	FOR(i,N[2]) A[2].push(0);
	
	int ret=0;
	FOR(i,K) {
		x=max(0,A[0].top());
		x=max(x,A[1].top()-T[0]);
		x=max(x,A[2].top()-T[0]-T[1]);
		ret=max(ret,x+T[0]+T[1]+T[2]);
		A[0].pop();
		A[1].pop();
		A[2].pop();
		A[0].push(x+T[0]);
		A[1].push(x+T[0]+T[1]);
		A[2].push(x+T[0]+T[1]+T[2]);
	}
	cout << ret << endl;
	
}

まとめ

これはすぐに思いつけて良かった。