AOJ 1297 Swimming Jam

問題

２レーンのプールでn人の人が泳ぐ。
それぞれのレーンは往路、復路の一方通行であり、レーンの幅は狭いため、
途中で泳いでる人を抜かすことはできない。

i番目の人は、レーンを片道泳ぐのにt[i]の時間がかかる。c[i]往復泳ぐとプールから出る。

前に、自分より遅い人が泳いでいてぶつかると、その人は前の人のペースに合わせて泳ぐ。
レーンの端にきてターンするときに、速い人は遅い人を抜かす。
３人以上が詰まっている場合も、同様にターンのときに抜かすことができる。

全員が泳ぎ終わるまでにかかる時間はいくらか、求めよ。

制約条件

n≦50

方針

キューを二つ使ってシミュレーションする。
今のレーンの端まで来る時間をキューに入れて、取り出していく。

前の遅い人にぶつかるというのは、キューに5, 3, 3, 3のように入っているときで、
キューの先頭以下の時間を全部一気に取り出して、
速い順に次のキューに入れれば衝突のあと抜かすというのをきちんと処理できる。

最初に、速い順にキューに入れなければならないことに注意する。

ソースコード

int n, c[50], t[50];
bool cmp(const pi &a, const pi &b){
	return t[a.F] < t[b.F];
}
int main(){
	while(cin >> n, n){
		rep(i, n) cin >> t[i] >> c[i];
		vector<pi> vv;
		rep(i, n) vv.pb(mp(t[i], i));
		sort(all(vv));
		queue<pair<int, pi> > q[2];
		rep(i, n) q[0].push(mp(vv[i].S, mp(vv[i].F, 0)));
		
		int cur = 0, next = 1, ans = 0;
		while(q[0].size() || q[1].size()){
			
			if(q[cur].empty()) swap(cur, next);
			else if(q[next].size() && q[cur].front().S.F > q[next].front().S.F) swap(cur, next);
			
			vector<pi> v;
			int nxt = q[cur].front().S.F;
			while(q[cur].size() && q[cur].front().S.F <= nxt){
				v.pb(mp(q[cur].front().F, q[cur].front().S.S));
				q[cur].pop();
			}
			sort(all(v), cmp);
			rep(i, v.size()){
				if(cur == 1) v[i].S++;
				if(v[i].S == c[v[i].F]) assert(ans <= nxt), ans = nxt;
				else q[next].push(mp(v[i].F, mp(nxt + t[v[i].F], v[i].S)));
			}
		}
		cout << ans << endl;
	}
	return 0;
}int n, c[50], t[50];
bool cmp(const pi &a, const pi &b){
	return t[a.F] < t[b.F];
}
int main(){
	while(cin >> n, n){
		rep(i, n) cin >> t[i] >> c[i];
		vector<pi> vv;
		rep(i, n) vv.pb(mp(t[i], i));
		sort(all(vv));
		queue<pair<int, pi> > q[2];
		rep(i, n) q[0].push(mp(vv[i].S, mp(vv[i].F, 0)));
		
		int cur = 0, next = 1, ans = 0;
		while(q[0].size() || q[1].size()){
			
			if(q[cur].empty()) swap(cur, next);
			else if(q[next].size() && q[cur].front().S.F > q[next].front().S.F) swap(cur, next);
			
			vector<pi> v;
			int nxt = q[cur].front().S.F;
			while(q[cur].size() && q[cur].front().S.F <= nxt){
				v.pb(mp(q[cur].front().F, q[cur].front().S.S));
				q[cur].pop();
			}
			sort(all(v), cmp);
			rep(i, v.size()){
				if(cur == 1) v[i].S++;
				if(v[i].S == c[v[i].F]) assert(ans <= nxt), ans = nxt;
				else q[next].push(mp(v[i].F, mp(nxt + t[v[i].F], v[i].S)));
			}
		}
		cout << ans << endl;
	}
	return 0;
}