コンテンツにスキップ

DOJ Beginner Contest 8 C - Mochi

サイト
DOJ
コンテスト
DOJ Beginner Contest 8
問題
C - Mochi

NN 個の餅があり、ii 番目の餅の大きさは AiA_i です。まだ使っていない餅を 2 個選んで 1 組にできますが、上に置く餅は下に置く餅より真に大きくなければなりません。作れる組の最大数を求める問題です。

テストケースは T≤2×105T \le 2 \times 10^5 個あり、NN の総和は 2×1052 \times 10^5 以下です。

AA を小さい順に並べ替えておきます。

kk 組作れるなら、小さいほうから kk 個を下に、大きいほうから kk 個を上に、それぞれ小さい順に組にしても作れます。つまり、すべての ii (1≤i≤k1 \le i \le k) で Ai<AN−k+iA_i < A_{N - k + i} が成り立つかを調べれば判定できます。

理由を説明します。kk 組作れたとして、下の餅を小さい順に b1≤⋯≤bkb_1 \le \dots \le b_k、上の餅を小さい順に t1≤⋯≤tkt_1 \le \dots \le t_k とします。

  • 下の餅のうち大きいほうから k−i+1k - i + 1 個は、どれも bib_i 以上です。その上の餅は、それより真に大きいので bib_i より大きくなります。よって、bib_i より大きい上の餅は k−i+1k - i + 1 個以上あり、ti>bit_i > b_i です。
  • 小さいほうから ii 番目の AiA_i は bib_i 以下、大きいほうから数えた AN−k+iA_{N - k + i} は tit_i 以上です。

まとめると Ai≤bi<ti≤AN−k+iA_i \le b_i < t_i \le A_{N - k + i} が成り立ちます。

kk 組作れるなら、そこから 1 組外せば k−1k - 1 組も作れます。そのため、作れる最大の kk を二分探索で求められます。kk は ⌊N/2⌋\lfloor N / 2 \rfloor 以下です。

計算量は、並べ替えと二分探索で O(Nlog⁡N)O(N \log N) です。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
A.sort()
ok = 0
ng = (N + 2) // 2
while ok + 1 < ng:
mid = (ok + ng) // 2
if all(A[i] < A[N - mid + i] for i in range(mid)):
ok = mid
else:
ng = mid
print(ok)

二分探索では、ok 組は作れて、ng 組は作れない、という状態を保っています。ng の初期値 ⌊N/2⌋+1\lfloor N / 2 \rfloor + 1 は、どうやっても作れない組数です。