AtCoder ABC 194 B – Job Assignment Python解説

スポンサーリンク

Job Assignment

あなたの会社には従業員 1 から従業員 N までの N 人の従業員がいます。
今あなたは仕事 A と仕事 B の 2 つの仕事を受注したので、これらを完了しなければなりません。
従業員 i は仕事 A を Ai分、仕事 B を Bi分でこなすことができます。
あなたは仕事 A と仕事 B にそれぞれ従業員を 1 人割り当てます。
同じ従業員を両方の仕事に割り当てても構いませんが、その場合 2 つの仕事が終わるのにかかる時間は、それぞれの仕事が終わるのにかかる時間の和となります。
仕事 A と仕事 B に異なる従業員を割り当てた場合、2 つの仕事が終わるのにかかる時間は、各仕事が終わるのにかかる時間の長い方となります。
2 つの仕事が終わるのにかかる時間として考えられる最小の値を求めてください。

AtCoder Beginner Contest 「Job Assignment」

for文の2重ループを使い、仕事Aと仕事Bに割り当てる従業員の組み合わせを全探索していきます。仕事Aと仕事Bが同じ従業員のときは、掛かる時間の和になるので注意しましょう。

n = int(input())

a, b = [0] * n, [0] * n

for i in range(n):
    a[i], b[i] = map(int, input().split())
    
ans = 1000000

for i in range(n):
    for j in range(n):
        if i != j:
            ans = min(ans, max(a[i], b[j]))
        else:
            ans = min(ans, a[i] + b[j])
            
print(ans)
            

配列aとbに仕事A,Bの時間を入れています。従業員が違う場合、2つの仕事が終わるのにかかる時間は、各仕事が終わるのにかかる時間の長い方となり、そのうちの最小を求めたいのでans = min(ans, max(a[i], b[j]))で計算しています。

従業員が同じ場合はかかる時間の和になるのでans = min(ans, a[i] + b[j])で計算します。
最後にansを出力して完了です。

AtCoder,未分類B問題

Posted by cheese