RedSpicaWS-8 Make Many Buri-Oden

問題

方針

答えを二分探索しました。

答えがmidにできるかどうかを判定する方法は、次の通りです。

・まずどれか1つぶりおでんセットをとる

・必要なぶりの個数、おでんの個数をそれぞれ計算する。

・あらかじめ、max_oden_list[b]: ぶりがb個以上ほしいときに取れるおでんの量 になってるリストmax_oden_listを作っておく。

・max_oden_list[必要なぶりの個数]>=必要なおでんの個数 になってたらok

・ダメだったら、他のぶりおでんセットで同じチャレンジをする。

・全部ダメだったら、答えをmidにすることはできません。ざんねん。

ACコード

from bisect import bisect_left

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

BO_list = [(a, b) for a, b in zip(A, B)]
BO_list.sort()

max_oden_list = [-1] * 200_001
for buri, oden in BO_list:
    max_oden_list[buri] = max(max_oden_list[buri], oden)

max_oden = -1
for i in range(200_000, -1, -1):
    max_oden = max(max_oden, max_oden_list[i])
    max_oden_list[i] = max_oden


def judge(m):
    for buri, oden in BO_list:
        need_buri, need_oden = m - buri, m - oden
        if max_oden_list[need_buri] >= need_oden:
            return True
    return False


left, right = 1, 200_000
while right - left >= 2:
    mid = (left + right) // 2
    if judge(mid):
        left = mid
    else:
        right = mid - 1
if judge(right):
    print(right)
else:
    print(left)