P9965 [THUPC 2024 初赛] 转化

jr_linys · 2023-12-20 11:10:05 · 题解

P9965 [THUPC 2024 初赛] 转化

2021/1/25 修改了细节。

赛时挂了两发，讲下我的思路。
有两个道具嘛，转换和分裂。

首先为了方便，我提出一个超空间的概念——球球本没有颜色，只是装他们的箱子有颜色，使用转化时，不着急确定放到哪个箱子，先放超空间里。

若初始有球，先把分裂用完。
不用转换就相当于转成自己，所以把球尽可能扔超空间里。

如果这时超空间里没球，那么结局已定。
考虑有球。

第一问

那些初始有球的已经没用了。
初始没球的就可能有用，如果转换 \ge1，那么可以扔一个球进去，它会吐出起码能回本或更多的球回超空间。
最后把超空间的球扔到你要的纸箱，注意不要算重自己的贡献。

第二问

把上面的操作做了，怎么算也不亏。
接下来都是没有球和转化的无赖，按照其分裂从大到小把超空间的球分出去。

实现仅供参考，时间复杂度 O(n\log n)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=351493;
int n,a[N+5],b[N+5],c[N+5],x[N+5],y[N+5],sum,add;
vector<int> v;

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=n;++i) cin>>b[i];
    for(int i=1;i<=n;++i) cin>>c[i];
    for(int i=1;i<=n;++i){
        if(a[i]){
            a[i]+=c[i],c[i]=0;
            x[i]=min(a[i],b[i]);//吐到超空间的球
            sum+=x[i];//总初始
        }else{
            if(b[i]>=1) y[i]=min(1+c[i],b[i])-1;//为超空间增加的球
            add+=y[i];//总增加
        }
    }
    if(sum==0){
        int ans=0;
        for(int i=1;i<=n;++i) ans+=a[i],cout<<a[i]<<' ';
        cout<<'\n'<<ans;
        return 0;
    }
    sum+=add;
    for(int i=1;i<=n;++i)
        if(a[i]) cout<<sum+a[i]-x[i]<<' ';
        else cout<<sum+c[i]-y[i]<<' ';

    int ans=sum;
    for(int i=1;i<=n;++i)
        if(a[i]) ans+=a[i]-x[i];
        else if(b[i]) ans+=(1+c[i])-(y[i]+1);
    for(int i=1;i<=n;++i) if(a[i]==0&&b[i]==0) v.push_back(c[i]);
    sort(v.begin(),v.end(),greater<int>());
    for(int x:v) if(sum-->0) ans+=x;
    cout<<'\n'<<ans;
}