DOJ Beginner Contest 8 C - Mochi
- サイト
- DOJ
- コンテスト
- DOJ Beginner Contest 8
- 問題
- C - Mochi
個の餅があり、 番目の餅の大きさは です。まだ使っていない餅を 2 個選んで 1 組にできますが、上に置く餅は下に置く餅より真に大きくなければなりません。作れる組の最大数を求める問題です。
テストケースは 個あり、 の総和は 以下です。
を小さい順に並べ替えておきます。
組作れるかの判定
Section titled “kkk 組作れるかの判定”組作れるなら、小さいほうから 個を下に、大きいほうから 個を上に、それぞれ小さい順に組にしても作れます。つまり、すべての () で が成り立つかを調べれば判定できます。
理由を説明します。 組作れたとして、下の餅を小さい順に 、上の餅を小さい順に とします。
- 下の餅のうち大きいほうから 個は、どれも 以上です。その上の餅は、それより真に大きいので より大きくなります。よって、 より大きい上の餅は 個以上あり、 です。
- 小さいほうから 番目の は 以下、大きいほうから数えた は 以上です。
まとめると が成り立ちます。
組作れるなら、そこから 1 組外せば 組も作れます。そのため、作れる最大の を二分探索で求められます。 は 以下です。
計算量は、並べ替えと二分探索で です。
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 の初期値 は、どうやっても作れない組数です。