Edit

【pythonでABC194を解説】B - Job Assignment

問題概要

問題ページ

B - Job Assignment
B - Job Assignment

問題ページへ移動する

問題文

あなたの会社には従業員 \(1\) から従業員 \(N\) までの \(N\) 人の従業員がいます。
今あなたは仕事 A と仕事 B の \(2\) つの仕事を受注したので、これらを完了しなければなりません。
従業員 \(i\) は仕事 A を \(A_i\) 分、仕事 B を \(B_i\) 分でこなすことができます。

あなたは仕事 A と仕事 B にそれぞれ従業員を \(1\) 人割り当てます。
同じ従業員を両方の仕事に割り当てても構いませんが、その場合 \(2\) つの仕事が終わるのにかかる時間は、それぞれの仕事が終わるのにかかる時間の和となります。
仕事 A と仕事 B に異なる従業員を割り当てた場合、\(2\) つの仕事が終わるのにかかる時間は、各仕事が終わるのにかかる時間の長い方となります。
\(2\) つの仕事が終わるのにかかる時間として考えられる最小の値を求めてください。

制約

  • \(2 \le N \le 1000\)
  • \(1 \le A_i \le 10^5\)
  • \(1 \le B_i \le 10^5\)
  • 入力に含まれる値は全て整数

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    ab = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    mn = 10 ** 20
    for i in range(n):
        for j in range(n):
            if i == j:
                mn = min(mn, ab[i][0] + ab[j][1])
            else:
                mn = min(mn, max(ab[i][0], ab[j][1]))
    print(mn)


if __name__ == '__main__':
    solve()

-Edit
-