题解 AT2672 【[AGC018C] Coins】

· · 题解

看完题可以发现这是一个类似于[NOI2019]序列的题目，自然考虑反悔贪心。

vp赛时本蒟蒻本来先考虑先选x个金币，再选y个银币，最后选z个铜币，在选每种币的时候把所有可以反悔的情况都开个堆维护，但是发现这样太复杂了，而且根本就没有利用总人数n=x+y+z的性质。

考虑因为n=x+y+z，所以可以先让所有人随便选一种硬币，保证x个人选了金币，y个人选了银币，z个人选了铜币，我们再进行反悔。

为方便，下文用x->y表示一个选了金币的人换成了银币，y->z,z->x等同理。

此时因为我们并不能改变选某种硬币的人数，所以我们能进行的变换只有类似于x->y，x->z，z->x这种环状的变换。略加思考可以发现只有5种情况：

1.x->y,y->z,z->x 2.x->z,z->y,y->x 3.x->y,y->x 4.y->z,z->y 5.x->z,z->x

然后一个人能进行的变换也只有6种，因此维护6个堆，然后每次对这5种情况找一个最大值即可（最大值<=0时答案达到最大值）

//W4P3R
#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define mp make_pair
#define pb push_back
#define re register ll
#define fr first
#define sd second
#define pa pair<ll,ll>
#define FOR(i,a,b) for(re i=a;i<=b;i++)
#define REP(i,a,b) for(re i=a;i>=b;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define N 100010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
inline ll read()
{
    char ch=getchar();
    ll s=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*w;
}
inline ll lowbit(ll x){return x&(-x);}
ll n,X,Y,Z;
ll a[N],b[N],c[N];
ll vis[N],ans;
priority_queue<pa,vector<pa>,less<pa> >q1,q2,q3,q4,q5,q6;
inline void add(ll x)
{
    q1.push(mp(b[x]-a[x],x));//x->y
    q2.push(mp(c[x]-b[x],x));//y->z
    q3.push(mp(a[x]-c[x],x));//z->x

    q4.push(mp(c[x]-a[x],x));//x->z
    q5.push(mp(b[x]-c[x],x));//z->y
    q6.push(mp(a[x]-b[x],x));//y->x
}
int main()
{
    //ios::sync_with_stdio(false);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    X=read(),Y=read(),Z=read();n=X+Y+Z;
    FOR(i,1,n)a[i]=read(),b[i]=read(),c[i]=read();
    FOR(i,1,X)vis[i]=1,ans+=a[i];
    FOR(i,X+1,X+Y)vis[i]=2,ans+=b[i];
    FOR(i,X+Y+1,X+Y+Z)vis[i]=3,ans+=c[i];
    FOR(i,1,n)add(i);
    while(true)
    {
        while(!q1.empty()&&vis[q1.top().sd]!=1)q1.pop();
        while(!q2.empty()&&vis[q2.top().sd]!=2)q2.pop();
        while(!q3.empty()&&vis[q3.top().sd]!=3)q3.pop();

        while(!q4.empty()&&vis[q4.top().sd]!=1)q4.pop();
        while(!q5.empty()&&vis[q5.top().sd]!=3)q5.pop();
        while(!q6.empty()&&vis[q6.top().sd]!=2)q6.pop();//反悔贪心在每次取值时弹出不合法状态往往更好写 

        ll v1=(q1.empty()?-inf:q1.top().fr),v2=(q2.empty()?-inf:q2.top().fr),v3=(q3.empty()?-inf:q3.top().fr);
        ll v4=(q4.empty()?-inf:q4.top().fr),v5=(q5.empty()?-inf:q5.top().fr),v6=(q6.empty()?-inf:q6.top().fr);
        ll maxn=0,t=0;
        if(v1+v2+v3>maxn)maxn=v1+v2+v3,t=1;//情况1
        if(v4+v5+v6>maxn)maxn=v4+v5+v6,t=2;//情况2
        if(v1+v6>maxn)maxn=v1+v6,t=3;//情况3
        if(v2+v5>maxn)maxn=v2+v5,t=4;//情况4
        if(v3+v4>maxn)maxn=v3+v4,t=5;//情况5
        if(!maxn)break;ans+=maxn;
        if(t==1)
        {
            ll x=q1.top().sd,y=q2.top().sd,z=q3.top().sd;
            vis[x]=2,vis[y]=3,vis[z]=1;
            add(x);add(y);add(z);
        }
        if(t==2)
        {
            ll x=q4.top().sd,y=q5.top().sd,z=q6.top().sd;
            vis[x]=3;vis[y]=2;vis[z]=1;
            add(x);add(y);add(z);
        }
        if(t==3)
        {
            ll x=q1.top().sd,y=q6.top().sd;
            vis[x]=2;vis[y]=1;
            add(x);add(y);
        }
        if(t==4)
        {
            ll x=q2.top().sd,y=q5.top().sd;
            vis[x]=3;vis[y]=2;
            add(x);add(y);
        }
        if(t==5)
        {
            ll x=q3.top().sd,y=q4.top().sd;
            vis[x]=1;vis[y]=3;
            add(x);add(y);
        }
    }
    cout<<ans<<'\n';
    return 0;
}
//gl

如果你觉得这篇题解对你有帮助，那你可以点个赞支持我一下qwq。如果你对题解有任何问题/认为我的题解有任何问题，可以私信/在评论区发出来，当然如果你对我的题解有任何意见/建议也欢迎指出。我会尽我全力把我题解写到最好的qwq