题解 CF436E 【Cardboard Box】

· · 题解

这里有一种基于反悔堆贪心的做法

建议大家先做一下两道类似的题（也可以搞懂这道题后用类似的方法做这两道）：

P1484 种树

[NOI2019]序列

这个题也可以用类似的做法来做

我们考虑怎么从选i颗星的方案拓展得到选i+1颗星的方案，有以下四种方式：

  1. 选择一个没有选星星的位置i，付出a_i的代价选一颗星

  2. 选择一个已经选了一颗星的位置i，然后付出(b_i-a_i)的代价选上第二颗星

  3. 选择一个已经选了一颗星的位置i，再选一个没有选星星的位置j，将原来i位置上选的那颗星星反悔不选，然后在位置j上选上两颗星，代价b_j-a_i

  4. 选择一个已经选了两颗星的位置i，再选一个没有选星星的位置j，将原来i位置上的第二颗星星反悔不选，再在j位置上选两颗星星，代价b_j-(b_i-a_i)

用堆每次从四种情况中选一种代价最小的拓展即可。

复杂度O(nlogn)

详细细节可以看代码：

#include<bits/stdc++.h>
using namespace std;
#define N 300007
#define LL long long
int a[N],b[N];
struct node{
    int x,i;
};
bool operator <(node a,node b){
    return a.x>b.x;
}
int ty[N];
struct queue  //可删除堆
{
    int op;
    priority_queue<node> q;
    void up(){while(!q.empty()&&ty[q.top().i]!=op)q.pop();}
    bool empty(){up();return q.empty();}
    node top(){up(); return q.top();}
    void push(node x){q.push(x);}
}q1,q2,q3,q4,q5;

void push1(int p){
    ty[p]=1;
    q2.push({b[p]-a[p],p}),q3.push({-a[p],p});
}
void push2(int p){
    ty[p]=2;
    q5.push({-(b[p]-a[p]),p});
}
void push0(int p){
    ty[p]=0; q1.push({a[p],p}),q4.push({b[p],p});
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
    q1.op=q4.op=0,q2.op=q3.op=1; q5.op=2;
    for(int i=1;i<=n;i++)
        q1.push({a[i],i}),q4.push({b[i],i});
    LL ans=0;
    for(int i=1;i<=m;i++){
        int x,mi=1e9+7,op=0,p,q;
        if(!q1.empty()&&(x=q1.top().x)<mi)mi=x,p=q1.top().i,op=1;  //情况1
        if(!q2.empty()&&(x=q2.top().x)<mi)mi=x,p=q2.top().i,op=2;  //情况2
        if(!q3.empty()&&!q4.empty()&&(x=q3.top().x+q4.top().x)<mi)mi=x,p=q3.top().i,q=q4.top().i,op=3;  //情况3
        if(!q5.empty()&&!q4.empty()&&(x=q5.top().x+q4.top().x)<mi)mi=x,p=q5.top().i,q=q4.top().i,op=4;  //情况4
        ans+=mi;
        if(op==1)push1(p);
        else if(op==2)push2(p);
        else if(op==3)push0(p),push2(q);
        else push1(p),push2(q);
    }
    printf("%lld\n",ans);
    for(int i=1;i<=n;i++)printf("%d",ty[i]); //因为每一次拓展都会把当前位置的状态记录下来，所以最后直接输出即可
    return 0;
}