洛谷P9965 [THUPC 2024 初赛] 转化题解

题目链接：P9965 [THUPC 2024 初赛] 转化

题意：

小 E 有 $n$ 种颜色的球，其中第 $i$ 种有 $a_i$ 个。有两类工具，第一类可以把一个指定颜色的球变成一个任意颜色的球；第二类可以把一个指定颜色的球变成两个这种颜色的球。一个变化之后的球也可以通过工具产生新的变化。关于第 $i$ 种颜色的第一类工具有 $b_i$ 个，第二类工具有 $c_i$ 个。小 E 想知道，如果每一个工具最多只能使用一次，那么对于每种颜色 $i$，第 $i$ 种颜色的球最后最多能有多少个。以及，小 E 最后最多能有多少个球。

输入格式：

第一行一个正整数 $n$。

第二行 $n$ 个整数，其中第 $i$ 个表示 $a_i$。

第三行 $n$ 个整数，其中第 $i$ 个表示 $b_i$。

第四行 $n$ 个整数，其中第 $i$ 个表示 $c_i$。

输出格式：

第一行 $n$ 个整数，其中第 $i$ 个表示如果每个工具最多使用一次，那么小 E 最后第 $i$ 种颜色的球最多有多少个。

第二行一个整数，表示如果每个工具最多使用一次，那么小 E 最后最多能有多少个球。

数据范围：

$1\le n \le 351493,~0\le a_i,b_i,c_i\le 10^9$。

这道题的思路非常巧妙。

不妨认为每个盒子有颜色，而其中的球没有标号，并钦定一个额外的盒子 $S$ 。

这样转换操作就可以将一个球移到 $S$ 中（从 $S$ 中移到盒子没有花费）。

如果一个盒子内初始有球，那么就把分裂操作全部用完，再尽量放到 $S$ 中。

操作结束后如果 $S$ 内没有球，那么显然这是最简单的情况。

考虑 $S$ 中有球的情况。此时有球的盒子已经没用了，而没有球的盒子如果有剩余的转换次数，

那么可以把 $S$ 中的一些球转移到这些盒子，显然这是不劣的。这样第一问实际上就解决了。

第二问只需将 $S$ 中的球按剩余分裂数从大到小放入盒子即可。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(4e5 + 15))

vector<int> v;
int sum,add,a[N],b[N],c[N],x[N],y[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; 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;
            down(x[i] = a[i], b[i]); sum += x[i];
        }else
        {
            if(b[i] > 0) down(y[i] = c[i], b[i] - 1);
            add += y[i];
        }
    }
    if(sum == 0)
    {
        int res = 0;
        for(int i = 1; i <= n; i++) {
            cout << a[i] << " \n"[i == n], res += a[i];
        }
        cout << res << '\n'; return 0;
    }
    sum += add;
    for(int i = 1; i <= n; i++) {
        if(a[i]) cout << sum + a[i] - x[i] << " \n"[i == n];
        else cout << sum + c[i] - y[i] << " \n"[i == n];
    }
    int res = sum;
    for(int i = 1; i <= n; i++) {
        if(a[i]) res += a[i] - x[i];
        else if(b[i]) res += (c[i] + 1) - (y[i] + 1);
    }
    for(int i = 1; i <= n; i++) {
        if(!a[i] && !b[i]) v.push_back(c[i]);
    }
    sort(v.begin(), v.end(), greater<int>());
    for(int i : v) if(sum > 0) { res += i, --sum; }
    cout << res << '\n';
    return 0;
}