Luogu P4053 [JSOI2007]建筑抢修

题目描述

https://www.luogu.com.cn/problem/P4053

简要题意：现在有 $n$ 个建筑需要修复，修复第 $i$ 个建筑需要 $t_i$ 秒，第 $i$ 个建筑需要在 $d_i$ 秒内进行修复才有效，求最多能修复多少建筑

$n\le 1.5\times 10^5$

Solution

因为所有建筑价值都相同，所以将建筑按照限制时间 $t_i$ 进行排序，用大根堆维护已经选的建筑，如果当前建筑不能选，则尝试去替换之前某一个耗时比它的大的建筑

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#define maxn 150010
#define ll long long
using namespace std;

int n; ll m; 

pair<int, int> a[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; 
    for (int i = 1; i <= n; ++i) cin >> a[i].second >> a[i].first;
    sort(a + 1, a + n + 1); 
    priority_queue<int> Q; 
    for (int i = 1, s = 0; i <= n; ++i) {
        if (s + a[i].second <= a[i].first) s += a[i].second, Q.push(a[i].second);
        else if (!Q.empty() && a[i].second < Q.top()) s -= Q.top() - a[i].second, Q.pop(), Q.push(a[i].second); 
    } cout << Q.size() << "\n"; 
    return 0;
}