題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟢 ARC146B Plus and AND

本題為 LeetCode 🔴 3806. Maximum Bitwise AND After Increment Operations 的原題，甚至完全相同。

Problem Statement

題目簡述

給定 $N$ 個非負整數。你最多可以執行 $M$ 次操作，每次選擇一個元素加 $1$ 。
操作完成後，需要從序列中選出 $K$ 個元素，最大化這 $K$ 個元素的 bitwise AND。

Constraints

約束條件

$1 \le K \le N \le 2 \times 10^5$
$0 \le M < 2^{30}$
$0 \le A_i < 2^{30}$
輸入皆為整數。

Example

Input 1

1 2	4 8 2 1 2 4 8

Output 1

解釋

可以把 $4$ 增加 $6$ 次變成 $10$ ，把 $8$ 增加 $2$ 次變成 $10$ 。
此時選出這兩個數，AND 為 $10$ 。無法得到更大的結果。

思路：試填法：從高位到低位試填答案

本題的核心是一個常見的二進位貪心模型：最大化某個 AND / OR / XOR 相關值時，先從最高位開始判斷這一位能不能變成 $1$ 。

如果最高位能變成 $1$ ，後面低位怎麼選都不會讓答案變差；如果最高位做不到，就只能放棄它，繼續看下一位。

為什麼可以逐位貪心？

AND 的某一位要是 $1$ ，代表被選出的 $K$ 個數在這一位都必須是 $1$ 。

因此，對於一個候選目標值，我們不要求每個被選出的數都等於它，而是要求每個數都「包含」它的所有 $1$ 位元。也就是說，每個被選出的數都要滿足：

x \ \&\ \text{target} = \text{target}

若能找到 $K$ 個數在加一後都滿足這個條件，那麼這 $K$ 個數的 AND 至少包含目標值的所有 $1$ 位元。

二進位最大化常用「從高位到低位試填」：先把已經確定能做到的高位保留下來，再嘗試把當前位設為 $1$ 。判定可行就保留，否則捨棄。

所以問題變成：

判定問題

假設目前希望答案至少包含某些已確定的 $1$ 位元，再加上正在嘗試的這一位，能不能用不超過 $M$ 次加一操作，找出 $K$ 個數，使它們都包含這些位元？

只要能回答這個判定問題，就可以從高位到低位構造最大答案。

單個數要補成目標，最少需要加多少？

接下來看判定問題的核心：對每個數，計算它至少要增加多少，才能包含目標值的所有 $1$ 位元。

如果它本來就已經包含目標的所有 $1$ 位元，成本就是 $0$ 。

否則，可以找出「最高的缺失位」：也就是目標值在這一位是 $1$ ，但目前數字在這一位是 $0$ ，並且這是所有缺失位中最高的一位。

因為加一會影響二進位的進位。若最高缺失位還是 $0$ ，低位怎麼調都沒有意義；必須先讓這一位變成 $1$ 。最小做法是：

保留比最高缺失位更高的部分。
讓最高缺失位透過進位變成 $1$ 。
把更低位整理成目標值要求的形狀。

舉例說明

例如目標位元是 $10110_2$ ，目前數字是 $11010_2$ 。

target = 10110
current = 11010
            ^
        最高缺失位

上述例子中，最小可行的新值是 $11110_2$ ，所以成本是 $11110_2 - 11010_2$ 。

定義 $cost(x, \text{target})$ 為把數字 $x$ 補成 $x' \enspace \& \enspace \text{target} = \text{target}$ 所需的 $+1$ 次數。

貪心：取成本最小的 K 個

固定候選目標後，每個數的角色就很單純：它能不能被選，只取決於「補成合法數需要多少次操作」。

既然要選出 $K$ 個數，並讓總操作次數不超過 $M$ ，最優選法一定是取成本最小的 $K$ 個。若連這 $K$ 個的總成本都超過 $M$ ，換成其他成本更高的數只會更差。

因此每次試填一個位元時，判定流程如下：

計算所有數補成候選目標的成本。
排序後取最小的 $K$ 個。
若總成本不超過 $M$ ，這一位可以保留為 $1$ 。

易錯點

每一輪判定時，不需要真的修改原陣列，也不需要固定上一輪選出的那 $K$ 個數。

判定只是在問「是否存在 $K$ 個數可以滿足目前目標」。最後一次成功保留下來的目標，自然會對應到某組可行的 $K$ 個數。

位數上界

答案不會超過「目前最大值加上所有可用操作次數」，因此枚舉到 $(\max A + M)$ 的二進位長度附近即可。

程式中從高到低枚舉可能位元。即使多檢查一個更高位，也會因成本超過操作上限而無法通過，不影響正確性。

正確性小結

從高位到低位試填，保證每次都優先決定更重要的高位。

固定候選目標時，每個數的補齊成本彼此獨立，取成本最小的 $K$ 個就是最優判定。因此，每次保留的位元都可行，每次捨棄的位元都不可行，最後得到的就是最大 AND。

複雜度分析

時間複雜度： $\mathcal{O}(N \log N \log U)$ ，其中 $U = \max A + M$ 。每個位元都會計算 $N$ 個成本並排序。
空間複雜度： $\mathcal{O}(N)$ ，排序成本列表需要額外空間。

排序瓶頸可以透過 Quick Select 優化

瓶頸在於每輪排序取前 $K$ 小成本。若使用 C++，可以改用 nth_element 做快速選擇，只找出前 $K$ 小的成本，不必完整排序，時間複雜度可優化為期望 $\mathcal{O}(N \log U)$ 。

Code

def solve():
    n, m, k = map(int, input().split())
    A = list(map(int, input().split()))
    assert len(A) == n

    B = (max(A) + m).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  # 把最高缺失位變成 1
                y |= tgt & ((1 << msb) - 1)  # 把低位整理成目標值要求的形狀
                return y - x

        if sum(sorted(cost(x) for x in A)[:k]) <= m:
            ans |= 1 << b
    print(ans)


if __name__ == "__main__":
    solve()

寫在最後

Cover Image Credit

The cover image was created by @bwm. All rights belong to the original artist.

It is used here only as a non-commercial cover illustration for this note. I do not claim ownership of the artwork.

If you are the copyright holder and believe this usage is inappropriate, please contact me by email or leave a comment. I will remove the image promptly.