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

🔗 Simultaneous Kagamimochi

Problem Statement

題目簡述

有 NN 個麻糬，大小已依非遞減順序排列。若一個麻糬的大小至多是另一個麻糬的一半，就能把較小者放在較大者上做成一組鏡餅。

每個麻糬最多只能使用一次，請求出最多可以同時做出幾組鏡餅。

Constraints

約束條件

  • 2≤N≤5×1052 \leq N \leq 5 \times 10^5
  • 1≤Ai≤1091 \leq A_i \leq 10^9
  • Ai≤Ai+1A_i \leq A_{i+1}
  • 所有輸入皆為整數

思路：貪心配對與可行性檢查

題目的核心是：從已排序的序列中選出若干小麻糬作為上層、同樣數量的大麻糬作為下層，並讓每一組都滿足「上層大小的兩倍不超過下層大小」。

基於貪心策略，如果要做出 KK 組鏡餅，最不浪費的選法是讓最小的 KK 個麻糬去當上層、最大的 KK 個麻糬去當下層。如果這種極端的分配方式都無法滿足條件，換成更大的上層或更小的下層必然也會失敗。

方法一：二分答案

可行性具有單調性：若能做出 KK 組鏡餅，則必然也能做出 K−1K-1 組。因此我們可以用二分搜尋來尋找最大的可行組數 KK。

在驗證候選數量 KK 是否可行時，我們將序列中最前方的 KK 個麻糬（作為上層）與最後方的 KK 個麻糬（作為下層）一對一依序檢查。只要每一對都滿足「上層的兩倍不大於下層」，就代表這個 KK 是可行的。

Warning

候選數量可以是 00，此時檢查應自然視為可行；二分範圍的右界最多是 ⌊N/2⌋\lfloor N / 2 \rfloor，因為每組鏡餅都需要兩個麻糬。

複雜度分析

  • 時間複雜度：O(Nlog⁡N)\mathcal{O}(N \log N)，二分搜尋 O(log⁡N)\mathcal{O}(\log N) 次，每次檢查 O(K)≤O(N)\mathcal{O}(K) \le \mathcal{O}(N)。
  • 空間複雜度：O(1)\mathcal{O}(1)。

方法二：二分答案 + 雙指標與前綴最大值預處理

這個預處理思路是 ABC388G 的解題關鍵

第二種方法仍然基於二分答案，差別在於我們先預處理出每個潛在上層的配對需求。這樣一來，每次驗證 KK 時就不必重新掃描 KK 對麻糬，能直接以 O(1)\mathcal{O}(1) 時間得出結論。

我們可以進一步優化驗證過程。針對每個可能作為上層的麻糬，可以利用雙指標找出它在序列中「最早能合法配對的下層位置」。

狀態定義：
為了方便對照實作與理解，我們依序定義以下狀態：

  1. 最早合法位置 (nxt[i]nxt[i])：對於第 ii 個麻糬，找到滿足大小條件的最小下層索引 jj。若不存在則為 NN。
  2. 跨越距離需求 (gap[i]gap[i])：該麻糬要配對到合法下層，至少需要在陣列中往右跨越的距離，即 gap[i]=nxt[i]−igap[i] = nxt[i] - i。
  3. 前綴最大需求 (preMax[i]preMax[i])：前 ii 個麻糬中，最大的跨越距離需求。

檢查條件推導：
若我們打算用最前方的 KK 個麻糬（索引 0…K−10 \dots K-1）來當上層，這群上層當中最嚴苛（需要跨越最遠）的距離需求，就是該截斷區間的「前綴最大需求」preMax[K−1]preMax[K-1]。
為了確保這 KK 個上層都能在剩餘的序列中找到對應下層，且不會超出陣列總長度，這 KK 個上層的最右側索引 (K−1)(K-1) 加上這段區間的最大跨越距離 preMax[K−1]preMax[K-1]，不能超過陣列的最大索引 (N−1)(N-1)。

也就是說，能組成 KK 組鏡餅的條件為：

(K−1)+preMax[K−1]≤N−1(K - 1) + preMax[K - 1] \le N - 1

化簡後為：

preMax[K−1]≤N−KpreMax[K - 1] \le N - K

若條件成立，則這 KK 組鏡餅必定能順利配對。透過 O(N)\mathcal{O}(N) 事先算好每個前綴區間的最大需求後，後續每次檢查 KK 的合法性只需 O(1)\mathcal{O}(1) 時間。

複雜度分析

  • 時間複雜度：O(N)\mathcal{O}(N)，其中雙指標預處理和前綴最大值計算各 O(N)\mathcal{O}(N)，二分搜尋 O(log⁡N)\mathcal{O}(\log N) 次，每次檢查 O(1)\mathcal{O}(1)。
  • 空間複雜度：O(N)\mathcal{O}(N)，用於儲存 nxtnxt 與 preMaxpreMax 陣列。

Code

方法一：二分答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
N = int(input())
A = list(map(int, input().split()))

# 是否可以組成 k 對麻糬
def check(k):
    for i in range(k):
        if A[i] * 2 > A[N - k + i]:
            return False
    return True

# 二分搜尋
left, right = 0, N // 2
while left <= right:
    mid = (left + right) // 2
    if check(mid):
        left = mid + 1
    else:
        right = mid - 1
print(right)  # 越小越合法，求最大的合法值

方法二：預處理最早可配位置

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
N = int(input())
A = list(map(int, input().split()))

# 計算下一個符合條件的位置
nxt = [0] * N
right = 0
for i in range(N):
    while right < N and 2 * A[i] > A[right]:
        right += 1
    nxt[i] = right

# 計算每個位置與下一個符合條件的位置的間距
gaps = [nxt[i] - i for i in range(N)]
pre = [0] * N
pre[0] = gaps[0]
for i in range(1, N):
    pre[i] = max(pre[i - 1], gaps[i])

# 是否可以組成 k 對麻糬
def check(k):
    return k - 1 + pre[k - 1] <= N - 1

# 二分搜尋
left, right = 0, N // 2
while left <= right:
    mid = (left + right) // 2
    if check(mid):
        left = mid + 1
    else:
        right = mid - 1
print(right)  # 越小越合法，求最大的合法值