一道经典的反悔贪心题。
考虑每次选择使总星数加一，那么总共有四种情况。
一、对于一关没有星，选一颗星，代价为 \(a_i\)。
二、对于一关有一颗星，再选一颗星，代价为 \(b_i-a_i\)。
三、对于一关有一颗星，选择退回这颗星，并再另一个没星的关卡选两颗星，代价为 \(-a_i+b_j\)。
四、对于一关有两颗星，退回一颗星，并再另一个没星的关卡选两颗星，代价为 \(-b_i+a_i+b_j\)
那么维护五个优先队列，分别为 \(a_i,b_i-a_i,-a_i,b_j,-b_i+a_i\)，每次取四种情况的最小值来选即可。
#include<iostream>
#include<cstdio>
#include<queue>
#define int long long
using namespace std;
const int N=3e5+5;
int n,w,a[N],b[N],vis[N];
long long ans=0;
struct node
{
int name;
int data;
};
bool operator <(node fi,node se)
{
return fi.data>se.data;
}
priority_queue<node>q1,q2,q3,q4,q5;
signed main()
{
scanf("%lld%lld",&n,&w);
q1.push({0,10000000000ll});
q2.push({0,10000000000ll});
q3.push({0,10000000000ll});
q4.push({0,10000000000ll});
q5.push({0,10000000000ll});
for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]),q1.push({i,a[i]}),q5.push({i,b[i]});
for(int i=1;i<=w;i++)
{
int num1=q1.top().data,num2=q2.top().data,num3=q5.top().data+q3.top().data,num4=q5.top().data+q4.top().data;
if(num1<=num2&&num1<=num3&&num1<=num4)
{
ans+=num1;
int id=q1.top().name;
vis[id]=1;
q3.push({id,-a[id]});
q2.push({id,b[id]-a[id]});
}
else if(num2<=num1&&num2<=num3&&num2<=num4)
{
ans+=num2;
int id=q2.top().name;
vis[id]=2;
q4.push({id,a[id]-b[id]});
}
else if(num3<=num2&&num3<=num1&&num3<=num4)
{
ans+=num3;
int id=q5.top().name,id2=q3.top().name;
q4.push({id,a[id]-b[id]});
q1.push({id2,a[id2]});
q5.push({id2,b[id2]});
vis[id]=2;
vis[id2]=0;
}
else
{
ans+=num4;
int id=q5.top().name,id2=q4.top().name;
q4.push({id,a[id]-b[id]});
q3.push({id2,-a[id2]});
q2.push({id2,b[id2]-a[id2]});
vis[id]=2;
vis[id2]=1;
}
while(q1.top().name!=0&&vis[q1.top().name]!=0)q1.pop();
while(q2.top().name!=0&&vis[q2.top().name]!=1)q2.pop();
while(q3.top().name!=0&&vis[q3.top().name]!=1)q3.pop();
while(q4.top().name!=0&&vis[q4.top().name]!=2)q4.pop();
while(q5.top().name!=0&&vis[q5.top().name]!=0)q5.pop();
}
printf("%lld\n",ans);
for(int i=1;i<=n;i++)printf("%lld",vis[i]);
return 0;
}