NC20154 [JSOI2007]建筑抢修（优先队列）

题意

有 $n$ 个任务，每个任务有个完成时间 $a_i$ 和截止时间 $b_i$ 。问最多能完成多少任务。 $n\leq 150000,t_1,t_2\leq 10^{18}$

分析

这道题还是挺难的QAQ。
首先看到这题，我们可以先将问题转化一下：
假设最终做的任务序列为 $x_i$ ，那么对任意 $i$ 需满足 $\sum\limits_{j=1}^{i}a_{x_j}\leq b_{x_i}$ ，也就是：

$n=1: a_{x_1}\leq b_{x_1}$
$n=2: a_{x_1} + a_{x_2}\leq b_{x_2}$
$n=3: a_{x_1} + a_{x_2} + a_{x_3}\leq b_{x_3}$
...

$n=k: a_{x_1}+a_{x_2}+...a_{x_k}\leq b_{x_k}$

我们现在要让这个序列尽量长。
然后有一个基础的想法：对于每个 $b_{x_i}$ ，我们要求满足上式的最长序列。然后对于同一个长度 $n$ ，肯定在合法的条件下，让 $\sum a_{x_i}$ 越小越好，因为这样能多出更多时间。
然后考虑暴力，我们可以对维护一个 $[1,n]$ 的 $pair$ ，每个 $pair$ 储存合法的长度和最小的前缀和。每次枚举到一个 $b_i$ ，更新所有合法的长度及其对应的最小前缀和（从 $n-1$ 更新到 $n$ ）。这样复杂度是 $O(n^2)$ 的。
要继续往下做，我们要发现： $n=k-1$ 和 $n=k$ 的序列仅仅差了一个数，这个数就是 $max\{a_{x_i}\}$ 。
于是，我们其实不用存 $[1,n]$ 的 $pair$ ，我们只用记录当前最长序列的前缀和 $t$ 和最大值 $v$ 即可。
如果 $t+a_i\leq b_i$ ，那么可以更新最长序列。
如果 $t+a_i > b_i$ ，那么如果 $v> a_i$ ，把 $v$ 换成 $a_i$ 只会使答案更优。（相当于是后悔之前的选择）
这种思想和求最长上升子序列的 $O(nlogn)$ 解法的思想有相似之处。
维护最大值可以用优先队列维护。最终复杂度是 $O(nlogn)$ 的。

代码如下

#include <bits/stdc++.h>
#define N 150005
using namespace std;
typedef long long LL;
LL z = 1;
LL read(){
    LL x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
priority_queue<LL> q;
struct node{
    LL t1, t2;
    bool operator < (const node & A) const{
        return t2 < A.t2;
    }
}d[N];
int main(){
    int i, j, n, m, ans = 0;
    LL t = 0, t1, t2;
    n = read();
    for(i = 1; i <= n; i++) d[i].t1 = read(), d[i].t2 = read();
    sort(d + 1, d + i);
    for(i = 1; i <= n; i++){
        t1 = d[i].t1, t2 = d[i].t2;
        if(t + t1 <= t2) t += t1, q.push(t1), ans++;
        else if(q.top() > t1) t += t1 - q.top(), q.pop(), q.push(t1);
    }
    printf("%d", ans);
    return 0;
}