Back to Leetcode

Readme

Greedy/2897.Apply-Operations-on-Array-to-Maximize-Sum-of-Squares/Readme.md

latest1.0 KB
Original Source

2897.Apply-Operations-on-Array-to-Maximize-Sum-of-Squares

我们遍历一下bit位的操作后果:

X  Y     AND OR
1, 1 =>   1  1
1, 0 =>   0  1
0, 1 =>   0  1
0, 0 =>   0  0

我们发现OR的效果其实是在每个bit位上“收集”1,而AND的效果其实就是“送出”1. 一进一出,不难发现X+Y= AND+OR。也就是说每次操作X和Y的一对数,我们在“零和”的前提下,拉大了“贫富差距”。这是我们想要的吗?是的,因为这能增大平方和。简单的证明,当x>=yd>0

(x+d)^2 + (y-d)^2 = x^2 + y^2 + 2d*(x-y) + 2d^2 > x^2 + y^2 

因为可以无限次操作,所以可以任意从某个元素出发,通过不断OR来“吸取”其他元素里各bit位上的1,直至构造出尽量大的元素。

代码中,我们统计每个bit上,nums里总共提供多少个1. 构造大数时,只需从最高位到最低位尽量填充1即可,如果没有库存了,就填充0. 最终取前k个大数,算一下平方和即可。