0%

100087. 对数组执行操作使平方和最大

100087.对数组执行操作使平方和最大

题目描述:

给你一个下标从 0 开始的整数数组 nums 和一个 整数 k

你可以对数组执行以下操作 任意次

  • 选择两个互不相同的下标 ij同时nums[i] 更新为 (nums[i] AND nums[j]) 且将 nums[j] 更新为 (nums[i] OR nums[j])OR 表示按位 运算,AND 表示按位 运算。

你需要从最终的数组里选择 k 个元素,并计算它们的 平方 之和。

请你返回你可以得到的 最大 平方和。

由于答案可能会很大,将答案对 $10^9 + 7$ 取余 后返回。

数据范围:

$1\le k \le nums.len \le 10^5; 1\le nums[i] \le 10^9$

题解:

x + y = x & y + x | y。因为两个数同一位同时为 $0$ 或 $1$ ,x & yx | y 同一位结果是不会变的,而同一位不同时,相当于交换了 $0,1$ 。即 $x$ 减少了 $d$ , $y$ 增加了 $d$ 。

假设原值: $x^2 + y ^2$ , $x < y$

交换后: $(x - d)^2 + (y + d)^2 = x^2 + y^2 + 2\times(y - x)\times d + 2d^2 \gt x^2 + y^2$ 。

通过交换之后数值变大了,因此应该通过交换,尽量得到更大的数。

可以考虑统计所有数的每一位上 $1$ 的个数。然后假设这些 $1$ 通过交换,全移动到了一个数上,这样就可以得到最大的数。每次这样进行,直到取出了 $k$ 个数,或者构造出的数为 $0$ 。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int maxSum(vector<int> &nums, int k)
{
int n = nums.size();
vector<int> cnt(31);
for (auto &x : nums)
{
for (int i = 30; i >= 0; --i)
{
if (x & (1 << i))
cnt[i]++;
}
}
long long ans = 0;
long long mod = 1e9 + 7;
while (k)
{
int x = 0;
for (int i = 30; i >= 0; --i)
{
if (cnt[i])
{
x += (1 << i);
cnt[i]--;
}
}
if(x == 0) break;
ans = (ans + 1ll * x * x % mod) % mod;
k--;
}
return ans;
}
};