【THUPC 2024 初赛】转化

我都能做出来，那就是大水题了。

思路

首先我们要确定最大可以变色的球的数量 \(tot\)。

有如下两个贪心步骤：

1. 所有颜色使用分裂操作，并更新 \(a_i\)。

此时的有 \(tot=\sum_{i=1}^n \min(a_i,b_i)\)（需要更新 \(a_i,b_i\)）。

1. 若 \(tot\) 大于 \(0\)，给 \(b_i\) 和 \(c_i\) 都不为 \(0\) 的点，分配一个球，执行完分裂 \(c_i\) 次后，更新 \(a_i,b_i\)，更新 \(tot\)。

这两个贪心步骤可以保证 \(tot\) 最大。

对于 1 如果一个点有球，那么从别处变色球来分裂肯定不优；对于 2，不难发现，执行完后 \(tot\) 肯定不降。

对于每一个颜色 \(i\)，如果此时 \(tot\) 大于 \(0\) 且 \(c_i\) 大于 \(0\)，那么 \(ans_i=tot+a_i+c_i\)。

如果 \(tot\) 等于 \(0\)，那么 \(ans_i=a_i\)。

对于全局最大值，在执行完上述操作中的 \(c_i\)，选择大于 \(0\) 且最大的 \(tot\) 个，设这些 \(c_i\) 的和为 \(sum\)。

全局最大答案为：\(ans=\sum\limits_{i=1}^n a_i+sum+tot\)。

时间复杂度 \(O(n)\)。

CODE

#include<bits/stdc++.h>
using namespace std;

const int maxn=5e5+5;

#define int long long
#define ll long long

struct node
{
    int c,id;
}edge[maxn];

ll n,fs,ct;
ll a[maxn],b[maxn],c[maxn];

bool cmp(ll a,ll b){return a>b;}

signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
    for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
    for(int i=1;i<=n;i++)
    {
        if(a[i]==0) continue;
        a[i]+=c[i];
        c[i]=0;
        ll t=min(a[i],b[i]);
        fs+=t;
        b[i]-=t;
        a[i]-=t;
    }
    for(int i=1;i<=n;i++)
    {
        if(b[i]&&c[i]&&fs)
        {
            fs--;
            a[i]=1+c[i];
            c[i]=0;
            ll t=min(b[i],a[i]);
            b[i]-=t;
            a[i]-=t;
            fs+=t;
        }
    }

    ll totans=0;
    for(int i=1;i<=n;i++)
    {
        totans+=a[i];
        ll t=fs+a[i];
        if(t) t+=c[i];
        printf("%lld ",t);
    }
    sort(c+1,c+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(c[i]&&fs)
        {
            fs--;
            totans+=1+c[i];
        }
    }

    printf("\n%lld",totans+fs);
}

赛时代码比较艹，所以读者自己写一次的好。