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

🔗 CF2183B Yet Another MEX Problem

rating: 1113

Problem Statement

題目簡述

給定長度為 nn 的陣列 AA 和整數 kk。

你需要執行 n−k+1n - k + 1 次操作：每次選擇一個長度為 kk 的區間 [l,r][l, r]，使得該區間的 mex\text{mex} 在所有長度為 kk 的區間中最大，然後從該區間中刪除任意一個元素。

最終剩下 k−1k-1 個元素，求剩餘元素的最大可能 mex\text{mex}。

Constraints

約束條件

  • 2≤k≤n≤2⋅1052 \le k \le n \le 2 \cdot 10^5
  • 0≤Ai≤1090 \le A_i \le 10^9

思路：鴿籠原理 (Pigeonhole Principle)

目標：在進行 n−k+1n-k+1 次操作後，將剩下 k−1k-1 個元素。我們的目標是最大化這 k−1k-1 個元素的 MEX。

1. 理論上界與冗餘元素

由於最終容器大小僅為 k−1k-1，即使我們填入最理想的數字 0,1,…,k−20, 1, \dots, k-2，能達成的最大 MEX 也被限制在 k−1k-1。因此 答案上界為 k−1k-1。

要達成 MEX=m=m，需要包含 0,1,…,m−10, 1, \dots, m-1 這 mm 個不同的數。為了達成最大的 MEX 值 k−1k-1，我們定義「有效元素」為數值 <k−1< k-1 且不重複的數字；反之則為「冗餘元素」：

  1. 數值過大：值 ≥k−1\ge k-1 的數字對答案無貢獻。
  2. 重複值：相同的數字只需保留一個。

2. 刪除冗餘元素

我們是否總能刪除「冗餘元素」而保留「有效元素」？

考慮操作規則：我們需在長度為 kk 的窗口中選擇一個數字刪除。

  • 窗口大小為 kk。
  • 可能的有效值範圍為 0,…,k−20, \dots, k-2，共 k−1k-1 種。

如果窗口中存在值 ≥k−1\ge k-1 的數字，則該數字對答案無貢獻，我們可以選擇刪除該數字。否則窗口內只有 0,…,k−20, \dots, k-2 這 k−1k-1 種數字，根據鴿籠原理，窗口中必存在重複的數字。因此，我們總能刪除冗餘元素。

既然每個窗口都必然包含冗餘元素，則題目要求的「選擇 max MEX 窗口」的約束實際上不影響最終答案，因為無論選擇哪個窗口，我們都能安全刪除冗餘元素

結論

由於操作只刪除不新增元素，所以任何剩餘子集的 mex 不可能大於原陣列 mex(A)。
最終能保留的 MEX 取決於原陣列本身能提供的 MEX，以及題目限制的容量 k−1k-1：

Ans=min⁡(mex(A),k−1)\text{Ans} = \min(\text{mex}(A), k-1)

複雜度分析

  • 時間複雜度：O(n)\mathcal{O}(n)。
  • 空間複雜度：O(n)\mathcal{O}(n)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    assert len(A) == n

    st = set(A)
    mex = 0
    while mex in st:
        mex += 1
    print(min(mex, k - 1))

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

寫在最後

PROMPT

masterpiece, best quality, high quality, good quality, 32K UHD, colorful, official art, illustration, in the style of fashion photography, dynamic, dynamic force picture, (Visual impact:1.2), impactful picture, extreme aesthetic, A shot with tension, sharp focus, The Ninth Art, depth of field, cinematic lighting, light particles, lens flare, movie perspective, (Tyndall Effect:1.4), light particles, light, shadow, scenery, temperate atmosphere, (artist:pigeon666:0.83), (Yomu:0.4), (remsrar:0.45), (quasarcake:0.3),

1girl, solo, Nijika Ijichi (ijichi nijika, bocchi the rock), brown eyes, blonde hair, long hair, very long hair, bangs, side ponytail, school uniform, white shirt, pleated skirt, long sleeves, bow, ahoge, sidelocks, outdoors, collared shirt, bowtie, black skirt, bag, red bow, red bowtie,

holding umbrella, transparent umbrella, rain, raining, night, wet street, puddle, reflection, glowing vending machine, backlighting, neon lights, urban scenery, wide shot, landscape, horizontal, looking at viewer, blush