🔗 🔴 3806. Maximum Bitwise AND After Increment Operations

Problem Statement

題目簡述

給定一個整數陣列與兩個整數 k,mk, m。你最多可以執行 kk 次操作，每次選擇一個元素加 11。
操作完成後，需要從陣列中選出大小為 mm 的子集合，最大化這些元素的 bitwise AND，並回傳最大可能值。

Constraints

約束條件

  • 1≤n=nums.length≤5×1041 \le n = \textit{nums.length} \le 5 \times 10^4
  • 1≤nums[i]≤1091 \le \textit{nums}[i] \le 10^9
  • 1≤k≤1091 \le k \le 10^9
  • 1≤m≤n1 \le m \le n

思路：試填法

本題和 ARC146B Plus and AND 完全相同，只要交換 kk 和 mm 的意義即可，請見 [解題紀錄]。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def maximumAND(self, nums: List[int], k: int, m: int) -> int:
        B = (max(nums) + k).bit_length()
        ans = 0
        for b in range(B, -1, -1):
            tgt = ans | (1 << b)
            def cost(x):
                if (x & tgt) == tgt:
                    return 0
                else:
                    msb = (tgt & ~x).bit_length() - 1
                    y = ((x >> msb) + 1) << msb
                    y |= (tgt & ((1 << msb) - 1))
                    return y - x
            if sum(sorted(cost(x) for x in nums)[:m]) <= k:
                ans |= (1 << b)
        return ans