ロープ本

ソース:白駿#2217
タイムアウトメモリ制限2秒192 MB

質問する

N(1≦N≦100000)本のロープがあります.このロープでこのような物体を持ち上げることができます.各ロープの太さや長さが異なると、持ち上げられる物体の重量が異なる可能性があります.
しかし、複数のケーブルを並列に接続すると、各ケーブルに必要な重量を区分することができる.k本のロープを用いて重量wの物体を持ち上げると、各ロープは平均してw/kの重量を必要とする.
各ケーブルに関する情報を取得する場合は、持ち上げられる物体の最大重量を解くプログラムを作成します.すべてのロープを使う必要はなく、何本かのロープを任意に選ぶことができます.

入力

最初の行は整数Nを与える.次のN本のロープには、各ロープが耐えられる最大重量が与えられる.この値は10000を超えない自然数です.

しゅつりょく

最初の行に答えを印刷します.

I/O例

入力例1

2
10
15

サンプル出力1

20

に答える

の意見を打診

まず逆順に各ロープを並べます.

各ケーブルのインデックス+1はこのケーブルの数を表しているので、ケーブルの数に自分(ケーブル)を乗じて割り当てることができる最大容量と考えられます.->greedy

使用可能容量の最大値を選択します.

説明する

インデックス+1(=行数)を適用するには、大きな値からソートする必要があるため、まず.sort(reverse=True)で逆順にソートします.

最後にリストから最大値を抽出すればよい.

python code

# 백준 2217번
from sys import stdin

def rope(n, weights):
    weights.sort(reverse=True)
    for i in range(1, n):       
        weights[i] = weights[i]*(i+1)      # 누적 합으로 만들기 

    # print("weights", weights)
    return max(weights)



n = int(stdin.readline())
weights = []
for i in range(n):
    weights.append(int(stdin.readline()))


result = rope(n, weights)
print(result)