1297-Swimming Jam

問題概要

往路と復路のあるプールがある．
往路と復路ともに非常に狭く追い抜きは出来ない．
ただし，一旦プールから出るときに，同時に出た人の仲で速い人が前になるように順番が調整される．
各個人の速度と往復回数が与えられるので，全員が泳ぎ終わるまでにかかる時間を求めよ．

解法

あるレーンで新規に泳ぐ人が泳ぎ終わるまでの時間は現在の時間をt，そのレーンで一番後ろにいる人が泳ぎ終わる時間をT，泳ぐ人の速度をvとすると
Max(T,t+v)となる．
後はqueueかdequeでシミュレーションするだけ．

実装(C++)

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <deque>
using namespace std;
typedef pair<int,int> P;
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define MAX(i,x) i=max(i,x);
#define until(q) while(!(q))
P p[50];int n;
int main(){
	while(cin>>n,n){
		REP(i,n){
			cin>>p[i].first>>p[i].second;
		}
		std::sort(p,p+n);
		deque<P> swim[2];
		int maxtime[2]={0,0};
		REP(i,n){
			swim[0].push_back(P(p[i].first,i));
			MAX(maxtime[0],p[i].first);
		}
		int now=0;
		for(now=0;now<10000000;now++){
			//レーン1で泳ぎ終わった人は居るか
			vector<int> tmp;
			while(swim[0].empty()==false&&swim[0].front().first==now){
				tmp.push_back(swim[0].front().second);
				swim[0].pop_front();
			}
			std::sort(tmp.begin(),tmp.end());
			REP(i,tmp.size()){
				MAX(maxtime[1],p[tmp[i]].first+now);
				swim[1].push_back(P(maxtime[1],tmp[i]));
			}

			//レーン2で泳ぎ終わった人は居るか
			tmp.clear();
			while(swim[1].empty()==false&&swim[1].front().first==now){
				tmp.push_back(swim[1].front().second);
				swim[1].pop_front();
			}
			std::sort(tmp.begin(),tmp.end());
			REP(i,tmp.size()){
				if(--p[tmp[i]].second==0)continue;
				MAX(maxtime[0],p[tmp[i]].first+now);
				swim[0].push_back(P(maxtime[0],tmp[i]));
			}
		}
		cout<<maxtime[1]<<endl;
	}
	return 0;
}