CF436E Cardboard Box解题报告

解题报告

CF436E Cardboard Box解题报告：

更好的阅读体验

题意

• $n$个关卡，每个关卡可以获得$0$星，$1$星和$2$星；
• 获得$1$星的代价为$a_i$，获得$2$星的代价为$b_i$；
• 求获得恰好$k$个星星的最小代价
• $1\leqslant n\leqslant 3\cdot 10^5,1\leqslant k\leqslant 2\cdot n$

分析

第一眼，很显然可以看出一个$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)$。

代码

需要注意的地方：

• long long，inf要开大
• 优先队列塞入边界值

#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;
}