C - Medicine

题目大意：

给 n 种药，第 i 种药吃 \(a_i\) 天，每天 \(b_i\) 粒。问最早在第几天，当天要吃的药 ≤ K 。
\(1<=n<=3*10^5\)
\(0<=k<=10^9\)
\(1<=a_i,b_i<=10^9\)

解题思路

首先了解了 n 种药，每次都是从第一天开始，持续 \(a_i\) 天，所以我当时直接想到用差分来做，数组初始全为 0 ，每次对 sum[1] + \(b_i\) ，对 sum[\(a_i+1\)] - \(b_i\) ，在最后要做前缀和的时候，发现虽然 n 的范围很小，但是 \(a_i\) 的跨度(\(10^9\))很大，不能遍历 sum 数组进行判断。

正确做法：使用 pair< int , int > 数组，储存 <\(a_i\),\(b_i\)>。数组大小为 n ，排个序。按照每种药的持续时间从小到大排列。然后遍历一次，求出第一天总共要吃多少粒药。之后遍历 pair 数组，减去当前种药的粒数，如果 ≤ K ，那么就说明在这种药的持续时间结束后，就永远的 ≤ K 了，答案就是p[i].second+1。还可能要全部吃完 = 0 才满足。

AC

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define IOS ios::sync_with_stdio(false),cin.tie(0);
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int MOD = 998244353;
const int N = 1e5 + 5;

//kmp kruskal lca 线段树 线性筛 组合数 线性同余方程
int n, k;

void solve () {
    cin >> n >> k;
    pair<int, int>p[n];
    for (int i = 0; i < n; ++i) {
        cin >> p[i].first >> p[i].second;
    }
    sort(p, p + n);
    ll sum = 0;
    for (int i = 0; i < n; i++)sum += p[i].second;
    if (sum <= k)cout << 1 << endl;
    else {
        for (int i = 0; i < n; i++) {
            sum -= p[i].second;
            if (sum <= k) {
                cout << p[i].first + 1;
                return;
            }
        }
        cout << p[n - 1].first + 1;
    }
}

signed main() {
    IOS
    int T;
    T = 1;
    //cin >> T;
    while (T--)solve();
    return 0;
}