はじめての「〜が 以下になる瞬間」を捉えるというシミュレーション問題。
問題概要
高橋君は 種類の薬を処方された。薬 は、 日目まで、毎日 錠ずつ飲むこととなる。
1 日に飲む錠剤の個数がはじめて 錠以下になる日を求めよ。
制約
考えたこと
シミュレーションすればよい。まず、1 日目に飲む錠剤の個数 ( の総和) を求めよう。
その後は、日数を経過するごとに飲む錠剤の個数は減少していく。減少イベントは次のように 回ある。
【減少イベント 】
日目には、飲む錠剤が 個減少する
これら 回の減少イベントをソートすることにする。つまり、 の値が小さい順にイベントを並び替える。なお、このような考え方をイベントソートと呼ぶ。
イベントをソートした順に処理していき、はじめて 錠以下になる瞬間を捉えればよい。計算量は となる。
コード
#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; }