[Programmers] LV2. 賠償コストを最小限に抑える


問題の説明
OO造船所は台風による操業遅延で予定通りに注文ができない船を想定している.期日どおりに完成できなければ、損害賠償をしなければならないので、残りの仕事量をデジタル化し、賠償費用を最小限に抑える方法を見つけたいです.
賠償費用に船舶1隻当たりの完成前の残りの作業量を乗じた.
造船所では、1時間以内に残ったことの中から1つを選んで、仕事量1で処理することができます.造船所で働くN時間と平日ごとの作業量の並び(works)では、賠償費用を最小化した結果を返す関数を作成してください.例えば、N=4の場合、各船舶の残量がworks=[4,3]の場合、賠償コストを最小化するために動作した結果は[2,2]、賠償コストは22+22+22=22=12となり、12に戻る.
せいげんじょうけん
  • 稼働時間N:10000000以下自然数
  • 配列作品サイズ:1000以下自然数
  • 毎日の作業量:1000以下の自然数
  • の意見を打診
    最大の要素は-1の順に減少します.この場合、Python heapqモジュールは最小のhipを提供するので、最大のhipを作成するには負の数に変換してheapソートを行うことができます.
    Python code
    import heapq
    def solution(no, works):
        if no > sum(works):
            return 0
        
        works = [-x for x in works]
        heapq.heapify(works)
    
        for _ in range(no):
            work = (-heapq.heappop(works)) -1
            heapq.heappush(works, -work)
        
        return sum([x ** 2 for x in works])