AtCoder-arc146_b Plus and AND

Plus and AND

贪心

从高位开始判断，判断每个数字当前位如果置为 \(1\) 需要多少步，如果当前位原本就是 \(1\)，则不消耗，如果原本不是，则消耗低位后，需要将低位全部置 \(0\)

然后排序，选消耗最少的 \(k\) 个，如果满足其消耗小于 \(m\)，直接默认该为置为 \(1\)，并保留之前的修改和消耗，继续判断下一位

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n, m, k;
    cin >> n >> m >> k;
    vector<ll>a(n);
    for(int i=0; i<n; i++) cin >> a[i];
    vector<ll>num(n, 0), temp(n);
    ll ans = 0;
    for(int i=31; i>=0; i--)
    {
        for(int j=0; j<n; j++)
        {
            temp[j] = num[j];
            if(a[j] >> i & 1) temp[j] += 0;
            else temp[j] += (1ll << i) - (a[j] % (1ll << i));
        }
        sort(temp.begin(), temp.end());
        ll sum = 0;
        int f = 0;
        for(int j=0; j<k; j++) sum += temp[j];
        if(sum <= m) f = 1;
        if(f)
        {
            ans |= 1ll << i;
            for(int j=0; j<n; j++)
            {
                if(a[j] >> i & 1) num[j] = num[j];
                else
                {
                    num[j] += (1ll << i) - (a[j] % (1ll << i));
                    a[j] = 0;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}