목차

The Milk Queue

ps
링크acmicpc.net/…
출처BOJ
문제 번호14778
문제명The Milk Queue
레벨플래티넘 4
분류

그리디

시간복잡도O(nlogn)
인풋사이즈n<=25000
사용한 언어Python 3.11
제출기록37144KB / 280ms
최고기록280ms
해결날짜2023/07/28

풀이

코드

"""Solution code for "BOJ 14778. The Milk Queue".

- Problem link: https://www.acmicpc.net/problem/14778
- Solution link: http://www.teferi.net/ps/problems/boj/14778

Tags: [greedy]
"""

import sys
import functools


def main():
    N = int(sys.stdin.readline())
    A_and_B = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    A_and_B.sort(
        key=functools.cmp_to_key(
            lambda x, y: (
                (x[0] - x[1]) - (y[0] - y[1])
                if (comp := min(x[0], y[1]) - min(x[1], y[0])) == 0
                else comp
            )
        )
    )

    first_barn_time = second_barn_time = 0
    for a, b in A_and_B:
        first_barn_time += a
        second_barn_time = max(second_barn_time, first_barn_time) + b

    print(second_barn_time)


if __name__ == '__main__':
    main()

,