题解：P11457 [USACO24DEC] Job Completion G

· · 题解

思路分析

前置题目：

P4053 [JSOI2007] 建筑抢修

P11328 [NOISG 2022 Finals] Gym Badges

这是一道反悔贪心，先考虑一种情况：

设 sum 为前 i-1 个工作所需时间。

若要使第 i 个工作和第 i + 1 个工作都可已完成，则必须至少要满足：

\begin{cases} sum \le s_i \\ sum + t_i \le s_{i+1} \\ t_i > 0 \end{cases}

化简得 s_i \le s_{i+1} 由此可以得出，我们可以对 s 进行升序排序。

排完序后再考虑一种情况：

如果 sum > s_i 此时要么不做，要么从前面去掉一个工作后再做，设前面 t 最大的一个下标为 k。

可知：

\begin{cases} sum > s_i \\ s_k \le s_i \\ sum - t_k \le s_k \end{cases}

所以可以得出：sum - t_k \le s_i

所以去掉一个最大的可以保证一定可以放下。

上代码：

#include <bits/stdc++.h>
using namespace std;
long long n, t;
struct ttt {
    long long v, e;
} a[600000];
bool cmp(ttt a, ttt b) {
    if (a.e == b.e) {
        return a.v < b.v;
    }
    return a.e+a.v < b.e+b.v;
}
int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        memset(a, 0, sizeof a);
        for (long long i = 1; i <= n; i++) {
            cin >> a[i].e >> a[i].v;
        }
        sort(a + 1, a + 1 + n, cmp);
        priority_queue<long long>q;
        long long ans = 0, anm = 0;
        for (long long i = 1; i <= n; i++) {
            q.push(a[i].v);
            ans++;
            anm += a[i].v;
            if (anm - a[i].v > a[i].e) {
                anm -= q.top();
                ans--;
                q.pop();
            }
        }
        cout << ans << endl;
    }
}