题解：CF2255D How Long Until Nothing Remains?

· · 题解

这题真简单吧。

不妨先固定操作次数 k，设第 j 次操作选择了 p_j。那么不难归纳得出，最终

a'_i=\left\lfloor\frac{a_i+\sum_{j=1}^{k}[p_j\neq i]2^{j-1}}{2^k}\right\rfloor

不妨设 w_i=\sum_{j=1}^k[p_j=i]2^{j-1}，那么式子变成

a_i'=\left\lfloor\frac{a_i+2^k-1-w_i}{2^k}\right\rfloor=\left\lceil\frac{a_i-w_i}{2^k}\right\rceil

我们希望最终 a_i'=0，因此对于所有 1\leq i\leq n，w_i\geq a_i。

问题转化为，有价值为 2^0,\cdots,2^{k-1} 的物品各一个，要把每个物品分配给一个 i，使得每个 i 分配到的物品的价值总和至少为 a_i。

考虑贪心。设 d_i 表示 i 当前还缺多少才能达到 a_i。用大根堆维护所有 d_i，按价值从大到小考虑每个物品，每次取出堆中最大的 d_i，把当前物品分配给 i 即可。

:::info[贪心正确性证明]

设当前未分配的最大价值为 w，最大的需求是 d_i。

若 d_i>w，则价值更低的物品的价值之和为 w-1，此时不把 w 分配给 d_i 必然不优。

若 d_i\leq w，设存在某种合法方案没有把 w 分配给 d_i，而是分配给了更小的 d_j，且分配给 d_i 的 w 之和为 S，那么把 S 分配给 d_j，w 分配给 d_i 显然合法。\Box

:::

考察合法的 k 的范围。首先要有 k\geq n。其次，若取 k=n+30，此时可用的权值包含 2^{30},\cdots,2^{n+29}，必然合法。因此我们只需要从小到大枚举 n\leq k\leq n+30 判断是否合法即可。

但是 2^{n+29} 级别的数显然不能直接计算。观察到指数 \geq 30 的大权值必然能消去恰好一个 d_i，而恰好有 \max(k-30,0) 个大权值，因此我们直接从 a 中去除前 \max(k-30,0) 大，剩下的再和 \leq 2^{29} 的小权值贪心即可。容易实现单次 \mathcal{O}(\log^2{V}) check。

时间复杂度为 \mathcal{O}(\sum n\log{n})，瓶颈在于排序。

:::success[代码]

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using i128 = __int128;
using ui = unsigned int;
using ull = unsigned long long;
using u128 = unsigned __int128;
using ld = long double;
using pii = pair<int, int>;
const int MAXN = 2e5 + 5;

template<typename T> T lowbit(T x) { return x & -x; }
template<typename T> void chkMin(T &x, T y) { x = y < x ? y : x; }
template<typename T> void chkMax(T &x, T y) { x = x < y ? y : x; }
constexpr int lg2(ll x) { return 63 ^ __builtin_clzll(x); }
constexpr ll bitCeil(ll x) { return x == 1 ? 1ll : 1ll << lg2(x - 1) + 1; }

int tc, n, a[MAXN];

bool check(int k) {
    int c = max(k - 30, 0);
    priority_queue<int> Q(a + 1, a + n + 1 - c);
    for (int i = min(k, 30) - 1; i >= 0 && !Q.empty(); --i) {
        int x = Q.top();
        Q.pop();
        if (x > (1 << i)) {
            x -= 1 << i;
            Q.emplace(x);
        }
    }
    return Q.empty();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> tc;
    while (tc--) {
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i];
        sort(a + 1, a + n + 1);
        for (int k = n; k <= n + 30; ++k) {
            if (check(k)) {
                cout << k << '\n';
                break;
            }
        }
    }
    return 0;
}

:::