AtCoderBeginnerContest423 D問題400点「Long Waiting」

https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d

問題概要

制約

気持ち

解法

時刻を管理する変数と $ Tとします。

団体客 $ iについて、一切待ちなく入れる場合は $ \max(T, A_i)に入れることになります。

$ A_iに到達したものの、 $ i -1番目の客の入店が想定より送れており $ T >A_iになっていることがありえるため、 max を取ります。

一方で、団体客 $ iが入ろうとしてもすんなり入れない可能性があります。

その場合、 $ i + A_i \leq Kとなるまで、もっとも早く退店する客を追い出せる時間まで $ Tを進ませなければいけません。

この「店内の客のうち、もっとも早く退店する時間」を求めるには priority_queueをつかえばいいです。

計算量

$ O(N \log N)

新たな学び

反省点

コード

code: cpp

int main() {

int n, k;

cin >> n >> k;

using P = pair<ll, ll>;

vector<ll> a(n), b(n), c(n);

rep(i, n) cin >> ai >> bi >> ci;

priority_queue<P, vector<P>, greater<P>> pq;

int in = 0;

ll time = 0;

for (int i = 0; i < n; i++) {

chmax(time, ai);

while (!pq.empty() && in + ci > k) {

in -= pq.top().second;

chmax(time, pq.top().first);

pq.pop();

}

cout << time << endl;

in += ci;

pq.push({time + bi, ci});

}