题解 P15699【[2018 KAIST RUN Spring] Touch The Sky】

· · 题解

Touch The Sky

说句闲话：2 月份的时候出了一场模拟赛，现在发现其中一题跟这题本质相同，遂前来贴个完整的证明。

把气球抽象成 n 个任务：每个任务需要花 D_i 的时间完成，需要在 L_i 时间之前开始——换句话说，需要在 L_i+D_i 时间前完成，相当于是个 DDL。问题转化成求最多有多少个任务能赶在 DDL 前完成。

重置一下记号，记完成所需要的时间为 a_i:=D_i，DDL 为 d_i:=L_i+D_i。将所有任务按 d_i 升序排序，维护前 i 个任务的最优安排方案。

用大根堆记录它们的 a 以及 \sum a。考虑第 i 个任务时先将 a_i 加入堆，若 \sum a\leq d_i 则将其计入答案，若 \sum a > d_i 就从堆中选出 a 最大的元素删去，这样就能实现答案最大化。时间复杂度 \mathcal{O}(n\log n)。

事实上，上面策略的证明不太美丽。思路大概分两步走：（1）按照截止时间排序一定是最优的；（2）丢掉运行时间最长的任务是最优的；具体证明过程如下。

引理 1. 若按 d_i 排序后有一个任务无法完成，则至少有一个任务无法完成。

证明. 第一个无法完成的任务 k 满足 \sum_{i\in[k]} a_i > d_{k}，假设有一种最优安排使得前 k 个任务都可以完成并且前 k 个任务中最后一个做的是 j，那么它的结束的时间至少为 \sum_{i\in[k]} a_i > d_{j}，矛盾。\qquad\Box

引理 2. 在排序策略下，若第一个无法完成的任务 k 将堆里弹出的任务是 m，则一定存在一个最优安排使得 m 被拒绝。

证明. 对任意一组最优安排，令其接受集合为 S，拒绝集合为 R:=[n]\,\backslash\,S。如果 m\notin R，就会存在 r\in [k] 使得 r\in R。

构造另一组安排 S^\prime = (S\,\backslash\,m)\cup r，根据引理 1，S 和 S^\prime 的任务都可以按照排序策略执行并且可以让 S 和 S^\prime 中前 k-1 个任务完成。S^\prime 中 k 结束的时间满足 \sum_{i\in [k]\,\backslash\,m} a_i \leq \sum_{i\in [k-1]} a_i \leq d_{k-1}\leq d_k，合法。

而由于 a_{r}\leq a_{m} 使得 S^\prime\,\backslash\,[k] 开始的时间一定早于 S\,\backslash\,[k]，一定不劣。因此 S^\prime 是一组最优安排。\Box

定理 3. 上述算法的构造是一组最优安排。

证明. 对最少无法完成的任务数 \textsf{REJ}(I) 使用归纳法。

若 \textsf{REJ}(I)=0，由引理 1 排序策略一定能完成所有任务，符合条件。

若 \textsf{REJ}(I)\geq 1，设第一个被弹出的任务是 m 并令 I^- = I\,\backslash\,m，根据引理 2 有 \textsf{REJ}(I^-) = \textsf{REJ}(I) -1。

上述算法给出的最优安排满足 S^{-}=S 且 R=R^{-}\cup m，故 |R|=\textsf{REJ}(I)。上述算法可以给出当前的最优安排，根据归纳法可知对所有集合成立。\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad\ \ \Box

代码实现如下：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=300010,INF=0x3f3f3f3f;
int n;
ll t,sum;
pair<ll,int> b[N];
priority_queue<int> q;
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        ll c,d;
        cin>>c>>d,b[i]={c+d,d};
    }
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++){
        auto [c,d]=b[i];
        sum+=d,q.push(d);
        if(sum>c)sum-=q.top(),q.pop();
    }
    cout<<q.size()<<'\n';
    return 0;
}