Codeforces Round #594 (Div. 1) C. Queue in the Train
問題ページ
基本的にやるべきことは問題文に書いてあるのでそのシミュレーションを行う.ただし, の範囲で を1ずつ増やしてシミュレーションをすると当然TLEなので,シミュレーションに関わってくる重要な時刻のみ取り扱う.人が席を立つ時刻 と水を汲み終わる時刻において状況が変化する.この時刻は 個しか存在しないため,高速にシミュレーションができる.
席を立てる人の集合 ,席を離れている人の集合 ,tankの前に並んでいる列 を持ちながら時刻を進めていく.priority_queueに状況が変わる時刻を追加し,最も早い時刻を取り出すとすれば,時刻を進める処理を実装できる.時刻 が席を立つ時刻なのか水を汲み終わる時刻なのかで処理が変わる.
- 席を立つ時刻
集合 に席を立つ人を追加する. - 水を汲み終わる時刻
今水を汲んでいる人が汲み終わる時刻として記録し, からその人を取り除く. にまだ人が並んでいるのであれば,その人が水を汲み始めるとする.
この処理のあと, の中で最も左にいる人が列に並ぶ条件を満たしているか?を判定する.列に並ぶならば, から削除, に追加, の最後尾に追加の処理を行うといった処理を行えばよい.
シミュレーションを行い時刻を進めるのに必要になる集合や列が何か?をしっかり整理して各時刻で行うべき処理をちゃんと詰める
#include <bits/stdc++.h> using namespace std; using ll = long long; using PII = pair<ll, ll>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template<typename T> void chmin(T &a, const T &b) { a = min(a, b); } template<typename T> void chmax(T &a, const T &b) { a = max(a, b); } struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio; #ifdef DEBUG_ #include "../program_contest_library/memo/dump.hpp" #else #define dump(...) #endif const ll INF = 1LL<<60; int main(void) { ll n, p; cin >> n >> p; vector<ll> t(n); REP(i, n) cin >> t[i]; using V = vector<ll>; priority_queue<V, vector<V>, greater<V>> event; REP(i, n) event.push({t[i], 0, i}); queue<ll> que; // tankの前の列 set<ll> can, leave; // 席を離れられる人, 席を離れてる人 vector<ll> ans(n); while(event.size()) { V v = event.top(); event.pop(); ll time = v[0], type = v[1], index = v[2]; if(type == 1) { ans[index] = time; leave.erase(index); que.pop(); if(que.size()) event.push({time+p, 1, que.front()}); } else { can.insert(index); } if(can.size()) { ll first = *can.begin(); if(leave.size() == 0 || *leave.begin() > first) { can.erase(first); leave.insert(first); que.push(first); if(que.size() == 1) event.push({time+p, 1, que.front()}); } } } REP(i, n) cout << ans[i] << (i==n-1?'\n':' '); cout << flush; return 0; } ``