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

huangyuze114514 · 2026-11-12 19:14:02 · 题解

算法：反悔贪心

思路

首先读完题后，显然能想到是反悔贪心。
题目求能引爆气球数量的最大值，那先想到的就是优先处理 L 低的啊，于是乎就有了如下代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
    long long d,l;
}a[250000];
long long n,cnt,ans,num;
priority_queue<long long>q;
bool cmp(node x,node y){
    return x.l<y.l;//按最高高度排序
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].l>>a[i].d;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        while(!q.empty()&&cnt>a[i].l){//当前高度太高
            num--;
            cnt-=q.top();//去掉升高高度最大的气球
            q.pop();
        }
        cnt+=a[i].d;
        num++;
        q.push(a[i].d);
        ans=max(ans,num);
    }
    cout<<ans;
    return 0;
}

但当我们提交后发现WA了。看以下例子：

3
2 4
3 1
5 2

正确答案是 2-1-3 答案就是 3，但是我们现在写的代码答案却是 2。
这是因为这份代码会在高度比当前处理的气球的 L 高时直接永久删去原队列中的气球，并无法返回。所以我们当前的反悔贪心思路是错误的。

那么考虑一下，什么处理顺序才能使用更多的气球呢？我们发现，肯定是当使用完当前气球后还能继续使用下一个气球的时候。那也就是说，如果使用完当前气球无法使用下一个气球，而两个气球交换一下就可以的时候，就需要交换一下两个气球的位置了。

于是考虑怎么排序。
设当前的高度为 cnt，有气球 i 和气球 j。那么如果先用气球 i 能后用气球 j，先用气球 j 却不能后用气球 i 了，即：

也就是

故

总上，当先选气球 i 再选气球 j，则须按 L+D 来排序。

在知道排序方法后，我们改变下贪心思路，若当前的高度高于当前处理气球的 L，那么删掉已处理的 D 最大的且比当前气球 D 大的气球即可。因为这样气球数量不变，高度反而降低，符合题意。

代码如下

#include<bits/stdc++.h>
using namespace std;
struct node{
    long long d,l;
}a[250000];
long long n,cnt,ans,num;//cnt当前高度,ans最大答案,num当前气球数量
priority_queue<long long>q;
bool cmp(node x,node y){
    return x.l+x.d<y.l+y.d;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].l>>a[i].d;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        //高度过高且存在比当前气球D高的
        if(cnt>a[i].l&&!q.empty()&&q.top()>a[i].d){
            num--;
            cnt-=q.top();
            q.pop();
        }
        //能用就用
        if(cnt<=a[i].l){
            cnt+=a[i].d;
            num++;
            q.push(a[i].d);
            ans=max(ans,num);
        }
    }
    cout<<ans;
    return 0;
}