这是一道构造题。
这题和按位或有关，可以拆位考虑，从大到小依次考虑答案的每一个二进制位。
假设现在考虑到第 位，如果有一个 的第 位是 ，那么不做任何操作一定是最优的。否则就考虑用 把 的第 位变成 。这样的代价是 。
从贪心的角度考虑，我们一定希望代价尽可能小，所以我们总是选择 最小的 ，即 最大。
这样，我们获得了 分。
这样操作之后 可能不为 ，考虑 的每一个为 的位 ，我们需要找到一个 ，使得 加上 后 的个数损失最小，它一定满足从第 位到最高位， 连续的 的格式最少。
然后就做完了。
Code
#include <bits/stdc++.h>
using namespace std;
long long a[1000010], b[1000010];
int bkt[70];
int main()
{
int c, T;
scanf("%d %d", &c, &T);
while(T--)
{
memset(bkt, 0, sizeof(bkt));
int n;
long long k;
scanf("%d %lld", &n, &k);
for(int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
b[i] = a[i];
}
for(int j = 60; j >= 0; j--)
{
bool OK = false;
for(int i = 1; i <= n; i++)
{
if(a[i] >> j & 1)
{
OK = true;
}
}
if(OK == false)
{
int x = 1;
long long val = (1ll << j);
for(int i = 2; i <= n; i++)
{
if(a[i] % val > a[x] % val)
{
x = i;
}
}
long long nxt = val - a[x] % val;
if(nxt <= k)
{
k -= nxt;
a[x] += nxt;
}
}
}
for(int j = 60; j >= 0; j--)
{
if(k >> j & 1)
{
int Min = 1e9, pos = 0;
for(int i = 1; i <= n; i++)
{
int cnt = 0;
for(int _ = j; _ <= 60; _++)
{
if(a[i] >> _ & 1)
{
cnt++;
}
else break;
}
if(cnt < Min)
{
Min = cnt;
pos = i;
}
}
a[pos] += (1ll << j);
k -= (1ll << j);
}
}
long long Max = 0;
for(int i = 1; i <= n; i++)
{
Max |= a[i];
}
printf("%lld\n", Max);
for(int i = 1; i <= n; i++)
{
printf("%lld ", a[i] - b[i]);
}
printf("\n");
}
return 0;
}
暂无评论