牛客练习赛136 D

我们记以二进制第 i 位为最高位且这一位为 1 时，其所有小于他的位之和一定小于这一位的值 枚举答案 x 的第 1−60 位为最高位，，我们选择第 i 位为最高位时，由 结论A，我们一定会选择所有第 i位为 0的所有值，一定不选第 i 位为 1 的值，否则一定不优。 这时记选择的这个集合为 S，考虑对于集合 S 枚举小于 i 的所有位，如果选择这一位对数组和的贡献大于 0，那么先选上，等选择完所有贡献大于 0 的位置后，再贪心的删除多余的位置。 现在我们选中了所有可以产生贡献的位置，这是选择第 i 位作为最高位时我们可以得到的最大贡献，现在我们考虑删除多余的一些贡献来使答案 x 最小。可知，删掉高位的贡献比删掉所有低位的贡献之和还要更高，所以从高到低枚举每一位，如果删掉这一位数组之和依然大于等于 y，那么删掉这一位是一定最优的做法

void solve()
{
    int n, y;
    cin >> n >> y;
    vi<int> a(n + 1);
    i64 sum = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    i64 ans = (1ll << 62);
    for (int i = 62; i >= 0; i--)
    {
        vi<int> pos;
        vi<int> pre(70);
        int now = 0;
        for (int j = 1; j <= n; j++)
        {
            if ((a[j] >> i) % 2 == 0)
            {
                pos.push_back(a[j]);
            }
        }
        for (int j = 0; j <= i; j++)
        {
            int num = 0;
            for (auto v : pos)
            {
                if ((v >> j) & 1)
                    num -= (1ll << j);
                else
                    num += (1ll << j);
            }
            pre[j + 1] = pre[j];
            if (num > 0)
            {
                pre[j + 1] += num;
            }
        }
        int ns = sum;
        for (int j = i; j >= 0; j--)
        {
            if (ns + pre[j] >= y)
            {
                continue;
            }
            else
            {
                now += (1ll << j);
                ns += pre[j + 1] - pre[j];
            }
        }
        if (pre[i + 1] + sum >= y)
            ans = min(ans, now);
    }
    cout << ans << endl;
}