CF2255D-题解

skyx · 2026-08-10 15:59:00 · 题解

题解-CF2255D

题目分析

对于某个数 x，在一次操作中：

设第 t 次操作，如果这个数没有被选中，记 c_t=1，否则 c_t=0；那么操作后 x_t=\left\lfloor\dfrac{x_{t-1}+c_t}{2}\right\rfloor。

同理，连续做 k 次操作，有 x_k=\left\lfloor \dfrac{x+c_1+2c_2+4c_3+\cdots+2^{k-1}c_k}{2^k}\right\rfloor；若要让最后结果为 0，就需要 x+c_1+2c_2+\cdots+2^{k-1}c_k<2^k。

移项有 x<2^k-(c_1+2c_2+\cdots+2^{k-1}c_k)。考虑这一坨 c ，因为每次只能选 1 个数，这个问题等价于：

• 有 k 个权值 1,2,4,\cdots,2^{k-1}，每个权值必须分给某一个 a_i，问能否让每个 a_i 分到的权值总和至少为 a_i。

考虑对于固定的 k 怎么做。比较明显的思路是贪心，能想到让当前最大的权值分给当前最大的数，正确性考虑 1+2+4+\cdots+2^{i-1} < 2^i 继而证明。

实时最大值可以用堆，但因为实际检查次数很少 sort 轰过去也行。

操作次数下界应该是 n，上界可以取 n+32，二分即可。暴力轰过去也行。

代码实现

注意开 long long，check 函数可以利用 a_i 的最值省掉很多麻烦。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define db double
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
const int N=2e5+10;
int a[N];
int b[N];
int n;
bool check(int k)
{
    for(int i=1;i<=n;i++)
    {
        a[i]=b[i];
    }
    int u=n;
    for(int i=k-1;i>=0 && u;i--)
    {
        if(i>=32 || (1ll<<i) >=a[u]) u--;
        else
        {
            a[u]-=(1ll<<i);
            sort(a+1,a+u+1);
        }
    }
    return u==0;
}
signed main()
{
    int sti=clock();

//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            b[i]=a[i];
        }
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++)
        {
            b[i]=a[i];
        }
        int l=n,r=n+32;
        int ans=-1;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(check(mid))
            {
                ans=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        cout<<ans<<endl;
    } 

//  cerr<<1.0*(clock()-sti)/CLOCKS_PER_SEC<<endl;
    return 0;
}