特に何事もなく終了。
http://codeforces.com/contest/644/problem/B
問題
並列処理のできないコンピュータを使い、計N個のクエリを捌く。
各クエリは時刻T[i]に要求が来る。各クエリをこなすにはD[i]の時間がかかる。
クエリが来た時点で、コンピュータがすでに他の処理で稼働中の場合、そのクエリはキューに積まれる。
ただしすでにキューにB個以上のクエリが詰まっている場合、そのクエリは破棄される。
キュー内のクエリは、コンピュータに余裕が出来た時点で先頭から消化される。
各クエリが破棄されるかどうか、されないなら終了時間を答えよ。
解法
Dequeを使い素直にシミュレートしよう。
Dequeには処理中のクエリ及びキューに積まれたクエリの終了時間を格納しておく。
各クエリを順次処理する。
まずDeque内で終了時刻がT[i]以前のものは追い出そう。
それでもまだDeque内のクエリがB個を超えるならクエリを破棄する。
そうでない場合、Deque内の最後のクエリの終了時刻(もしくはDequeが空ならT[i])からそのクエリを開始し、D[i]後に終わると考えて良い。
int N,B; ll ret[202020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>B; deque<ll> D; FOR(i,N) { cin>>x>>y; while(D.size() && D.front()<=x) D.pop_front(); if(D.size()==0) { ret[i]=x+y; D.push_back(ret[i]); } else if(D.size()<=B) { ret[i]=D.back()+y; D.push_back(ret[i]); } else { ret[i]=-1; } } FOR(i,N) cout<<ret[i]<<" "; cout<<endl; }
まとめ
結局愚直に実装するだけだし、Div2B位?