【ABC189 C】「Mandarin Orange」を解く【Python3】

コンテスト一覧へ

 

Ai 個のみかんが置かれている N 枚の皿が並べられており、「l 番目~ r 番目」のすべての皿からみかんをx個(≦Ai)ずつ取って食べるとき、食べることができる最大の数を求める問題です。

提出
n = int(input())
a = list(map(int, input().split()))
ans = 0

for i in range(n):
    mikan = a[i]
    for j in range(i,n):
        mikan = min(mikan, a[j])
        ans = max(ans, (j-i+1)*mikan)

print(ans)

入力はすべて整数です。

l 番目~r 番目」の (l, r) の組を全探索することで求めることができます。

1つの皿から取って食べることができるみかんの数は、「l 番目~ r 番目」の間にある Ai の最小値となります。

「mikan = a[i]」の所で、l 番目のみかんの数を mikan に代入します。

その後ろの r 番目をすべて探索し、a[j] の数の方が小さい場合に、mikan に入れます。

「(j-i+1)*mikan」は取って食べたみかんの総数です。これと ans を比較して大きい方を ans に入れます。

すべて探索した後に、ansに入っている数字を出力します。

【ABC189】解説記事リスト

コンテスト一覧に戻る