問題概要

高橋君は $N$ 種類の薬を処方された。薬 $i$ は、 $1, 2, \dots, a_{i}$ 日目まで、毎日 $b_{i}$ 錠ずつ飲むこととなる。

1 日に飲む錠剤の個数がはじめて $K$ 錠以下になる日を求めよ。

制約

$1 \le N \le 3 \times 10^{5}$

考えたこと

シミュレーションすればよい。まず、1 日目に飲む錠剤の個数 ( $b_{i}$ の総和) を求めよう。

その後は、日数を経過するごとに飲む錠剤の個数は減少していく。減少イベントは次のように $N$ 回ある。

【減少イベント $(a_{i}, b_{i})$ 】
$a_{i} + 1$ 日目には、飲む錠剤が $b_{i}$ 個減少する

これら $N$ 回の減少イベントをソートすることにする。つまり、 $a_{i}$ の値が小さい順にイベントを並び替える。なお、このような考え方をイベントソートと呼ぶ。

イベントをソートした順に処理していき、はじめて $K$ 錠以下になる瞬間を捉えればよい。計算量は $O(N \log N)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;
using pll = pair<long long, long long>;

int main() {
    long long N, K, num = 0, res;
    cin >> N >> K;
    
    // (a, b) を a が小さい順にソートする
    vector<pll> ab(N);
    for (int i = 0; i < N; ++i) {
        cin >> ab[i].first >> ab[i].second;
        num += ab[i].second;  // num: 初日時点の薬の個数
    }
    sort(ab.begin(), ab.end(), [&](pll x, pll y){return x.first < y.first;});
    
    // 最初から K 個以下の場合の答えは 1
    if (num <= K) {
        cout << 1 << endl;
        return 0;
    }
    
    // シミュレーション
    for (auto [a, b] : ab) {
        num -= b;  // a + 1 日目には錠剤が b 個減る
        if (num <= K) {
            res = a + 1;
            break;
        }
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 309 C - Medicine (3Q, 灰色, 350 点)

問題概要

制約

考えたこと

コード