题解 CF436E 【Cardboard Box】

· · 题解

CF436E Cardboard Box解题报告：

更好的阅读体验

题意

分析

第一眼，很显然可以看出一个O(n\cdot k)的dp做法（设f_{i,j}代表前i个关卡获得j个星星的最小代价），但是这个复杂度无法通过本题。

首先，可以使用一个贪心思想：每一次增加一颗星星，取最小的增加方式。

我们考虑一个贪心策略：不断选最小a_i的零星关卡改成一星关卡，或者把一个一星关卡改成二星关卡（贪心地选已经有一星且b_i-a_i最小的关卡），但是这个贪心很显然是错误的。

hack：

2 3
4 1
1 9

普通贪心不行，我们可以进行反悔贪心，建议先做一道题了解一下反悔贪心：CF865D Buy Low Sell High。

重申一下贪心的思想：每一次增加一颗星星，取最小的增加方式。

此时贪心策略有两种：

  1. 零星关卡i改一星关卡i；
  2. 一星关卡i改二星关卡i。

想一想怎么通过反悔之前的操作来增加一颗星星（即反悔策略）：

  1. 一星关卡i改零星关卡i，并将一个零星关卡j改成二星关卡；
  2. 二星关卡i改一星关卡i，并将一个零星关卡j改成二星关卡。

注意，普通贪心二并不能归入反悔贪心一，因为反悔策略一本质是把一个零星关卡改成二星关卡，而贪心策略二本质是把一个一星关卡改成二星关卡，在维护时会有差别。

现在考虑如何维护这四个策略： （注意，代码中小根堆是用大根堆权值取负来实现的）

  1. 贪心策略1：对答案的贡献为a_i，用小根堆q1来维护零星关卡的a；
  2. 贪心策略2：对答案的贡献为b_i-a_i，用小根堆q5来维护一星关卡的b-a；
  3. 反悔策略1：对答案的贡献为b_j-a_i，我们可以把式子拆成b_j和-a_i，用小根堆q3维护零星关卡b的最小值，用大根堆q2维护一星关卡a的最大值；
  4. 反悔策略2：对答案的贡献为b_j+a_i-b_i，我们可以把式子拆成b_j和-(b_i-a_i)，用小根堆q3维护零星关卡b的最小值，用大根堆q4维护二星关卡b_i-a_i的最大值。

还要注意一个细节：有些关卡星值的修改会牵扯到两个堆，此时我们就不能单纯只\text{pop}当前的状态了，还要在每一次取状态时判断状态是否满足，不满足就直接\text{pop}掉。

注意这里可以直接\text{pop}的原因是反悔之后的关卡一定不会再次进行反悔。（否则就一定不优了）

时间复杂度：因为每个点最多进行一次贪心选出，一次反悔，加上优先队列，故复杂度为：O(n\log n)。

代码

需要注意的地方：

#include<stdio.h>
#include<queue>
#define int long long
#define inf 100000000000000000
using namespace std;
const int maxn=300005;
int n,m,anss;
int a[maxn],b[maxn],ans[maxn];
priority_queue< pair<int,int> >q1,q2,q3,q4,q5;
//q1 min{a|a选0}
//q2 max{a|a选1}
//q3 min{b|b选0}
//q4 max{b-a|b选2}
//q5 min{b-a|a选1}
inline void add_0(int x){//加入0
    ans[x]=0;
    q1.push(make_pair(-a[x],x));
    q3.push(make_pair(-b[x],x));
}
inline void add_1(int x){//加入1
    ans[x]=1;
    q2.push(make_pair(a[x],x));
    q5.push(make_pair(-(b[x]-a[x]),x));
}
inline void add_2(int x){//加入2
    ans[x]=2;
    q4.push(make_pair(b[x]-a[x],x));
}
signed main(){
    scanf("%lld%lld",&n,&m);
    //优先队列插入初值
    q1.push(make_pair(-inf,n+1));
    q2.push(make_pair(-inf,n+1));
    q3.push(make_pair(-inf,n+1));
    q4.push(make_pair(-inf,n+1));
    q5.push(make_pair(-inf,n+1));
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&a[i],&b[i]);
        add_0(i);//初始星值是0
    }
    for(int k=1;k<=m;k++){//不断增加一个星星
        int p1=q1.top().second,p2=q2.top().second,p3=q3.top().second,p4=q4.top().second,p5=q5.top().second;
        while(q1.size()>1&&ans[p1]!=0)
            q1.pop(),p1=q1.top().second;
        while(q2.size()>1&&ans[p2]!=1)
            q2.pop(),p2=q2.top().second;
        while(q3.size()>1&&ans[p3]!=0)
            q3.pop(),p3=q3.top().second;
        while(q4.size()>1&&ans[p4]!=2)
            q4.pop(),p4=q4.top().second;
        while(q5.size()>1&&ans[p5]!=1)
            q5.pop(),p5=q5.top().second;
        int k1=-q1.top().first,k2=q2.top().first,k3=-q3.top().first,k4=q4.top().first,k5=-q5.top().first;
        int t1=k1,t2=k5,t3=k3-k2,t4=k3-k4;
        int minn=min(min(t1,t2),min(t3,t4));
        //注:这里i指已选的点，j指未选的点
        if(t1==minn){
            //贪心策略1:选一星(0->a[i])
            anss+=t1;
            q1.pop();
            add_1(p1);
        }
        else if(t2==minn){
            //贪心策略2:一星改成二星(a[i]->b[i])
            anss+=t2;
            q5.pop();
            add_2(p5);
        }
        else if(t3==minn){
            //反悔策略1:一个一星改零星，选另一个二星(a[i]->b[j])
            anss+=t3;
            q2.pop(),q3.pop();
            add_0(p2),add_2(p3);
        }
        else{
            //反悔策略2:一个二星改一星，选另一个二星(b[i]->a[i]+b[j])
            anss+=t4;
            q3.pop(),q4.pop();
            add_1(p4),add_2(p3);
        }
    }
    printf("%lld\n",anss);
    for(int i=1;i<=n;i++)
        printf("%lld",ans[i]);
    puts("");
    return 0;
}