题解：P16939 后记

Build_Dreams · 2026-06-14 21:48:32 · 题解

贪心题。

我们将所有模块按照 t_i 排序然后依次处理每个模块。

首先对题目式子进行简化。

条件是：

简单移项：

于是问题变成了，给定你一个数列 a，长度为 n，要求删去最少的数字，使得每一个前缀和都是非负的。

前缀和非负可以考虑反悔贪心，对于每一个点，我们考虑加入这个点，并将返回的代价加入优先队列。

如果加入这个点过后，发现和小于 0，那么，从优先队列中取出最大的若干个数字进行反悔直到当前的和非负。

反悔的代价就是代价的相反数。

然后统计一下反悔次数就做完了。

code

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define piii pair<pii, int>
#define pll pair<ll, ll>
#define plll pair<pll, ll>
#define fi first
#define se second
const int N = 2e5 + 5, M = 1e6 + 5;
const int inf = 1e9, mod = 998244353;
const ll INF = 1e18;

namespace ARIS0_0{
    int n;
    piii a[N];

    void init(){
    }
    bool cmp(piii a, piii b){
        return a.se < b.se;
    }
    void solve(){
        cin >> n;
        for (int i = 1; i <= n; i ++ ) cin >> a[i].fi.fi >> a[i].fi.se >> a[i].se;
        sort(a + 1, a + n + 1, cmp);

        ll now = 0, cnt = 0;
        priority_queue <ll> q;
        for (int i = 1; i <= n; i ++ ){
            now += a[i].fi.se - a[i].fi.fi;
            q.push(-(a[i].fi.se - a[i].fi.fi));
            if (now < 0){
                while (now < 0) now += q.top(), q.pop(), cnt ++;
            }
        }

        cout << cnt << "\n";
    }
    void single(){ init(), solve(); }
    void multi(){ init(); int T; cin >> T; while (T -- ) solve(); }
    void idmulti(){ init(); int id, T; cin >> id >> T; while (T -- ) solve(); }
};

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ARIS0_0::single();
}

/*
 * 
 * 
 * 
 */