题解 P5909 【[CTSC2007]挂缀pendant】

· · 题解

这是一道比较经典的反悔贪心。原来CTSC还有这样的水题。

什么是反悔贪心呢？用通俗的话讲，由于贪心只注重当前的最优解，有时候无法得到全局最优解。反悔贪心就是在发现比当前最优解还要优时进行反悔操作。

看到这道题，题意大致可以理解为：给你 N 个区间，规定区间的的长度为 W_i ,左端点不能超过 C_i ，要使得区间个数最多，并且使得区间长度之和最小。

这里我们不妨定义一个数组 R_i ，表示第 i 个区间的右端点不超过 R_i ，R_i 在数值上等于 C_i+W_i ，那么贪心策略又是什么？

我们不妨设 R_1 \leq R_2 \leq R_3 \leq \dots \leq R_N ,此时我们已经选出了满足要求的若干个区间，记这些区间的长度总和为 S ，区间长度的最大值为 MAX ，现在循环到了第 k 个区间，如果发现 S+W_k \leq R_k ，那么代表当前区间可以被选择，则区间个数加一，区间长度加 W_k ，否则，如果S+W_k > R_k，那么代表当前区间就没有用了吗？不对，因为题目还有一个条件——要使区间长度之和最小。为了使每一个区间都物尽其用，我们还可以将 W_k 和 MAX 相比较，如果 W_k < MAX，则可以将长度为 MAX 的区间从原来满足要求的区间们中取出，重新插入当前的区间，还要记得更新区间的总长度。那如果 W_k \geq MAX 呢？那这个区间是真的没用了。

说了一堆，反悔在哪呢，就是在取出长度为 MAX 的区间，插入当前的区间中。一般贪心是没有这个操作的。为了取得全局最优值，只能舍弃掉一些相对更劣质的决策，加入更优质的决策。

最大值可以用堆来维护。

贴上代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+2;
#define int long long
struct interval{
    int len,r;
    bool operator <(const interval & x)const{
        return r<x.r;
    }
}a[MAXN];
int f[MAXN];
int n,num,sum;
priority_queue<int>qu;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].r>>a[i].len;
        a[i].r+=a[i].len;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        if(sum+a[i].len<=a[i].r){
            num++;
            sum+=a[i].len;
            qu.push(a[i].len);
        }
        else if(qu.top()>a[i].len){
            sum-=qu.top();
            qu.pop();
            qu.push(a[i].len);
            sum+=a[i].len;
        }
    }
    cout<<num<<endl<<sum<<endl;
    return 0;
}