题解 CF436E 【Cardboard Box】

这里有一种基于**反悔堆贪心**的做法 建议大家先做一下两道类似的题（也可以搞懂这道题后用类似的方法做这两道）： [P1484 种树](https://www.luogu.com.cn/problem/P1484) [ [NOI2019]序列](https://www.luogu.com.cn/problem/P5470) 这个题也可以用类似的做法来做 我们考虑怎么从选$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)$ 详细细节可以看代码： ```cpp #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; } ```