[BOJ-2217]ケーブル(Python)

4223 ワード
python ps テキストリンク

🤒 質問する


BOJ-2217ケーブル

💊 に答える


  • 例えば、ケーブルが耐えられる最大重量は10, 15, 20, 35, 30であると仮定する.

  • このリストを降順に並べなさい.35, 30, 20, 15, 10

  • ロープを1本使えば、最大重量は35です.

  • 2本のロープを使えば、最大重量はWです.
    では、1本のロープが持ち上げられる最大重量は(W / 로프갯수)、つまりW/2であるべきです.
    降順2本のロープは35, 30で、そうするとW/2 <= 30になります.なぜなら、2本のロープを使うには、W/2が30より大きいと、1本のロープしか使えないからです.
    • そしてゆっくり考えて、答えは
    各ケーブルが耐えられる最大重量のリストを降順に並べ、1+1本のケーブルを使用する場合の最大重量Wは.
    W=並べ替えリストのi要素*(i+1)
    表示されます.
    解が終わった後にネット上で多くの他の人の解を調べて、多くの解はWを求める方式を通じて回転したのです.しかしそうなると時間的に複雑度がO(N 2)O(N^{2})O(N 2)になるので暗くなる.
    heapqを用いて,heappush()の時間的複雑度をO(logn)O(logn)O(logn)O(logn)O(logn)とし,N回繰り返すとO(Nlogn)O(logn)の時間的複雑度が得られる.もっと良い資料構造を思い浮かべればいいのですが、私が今考えているものの中でヒップホップが一番です.😉 Pythonのheapqモジュール
  • heapqモジュールの概要
    • 片付けました.

    ソースコード

    import sys
import heapq

N = int(input())
weight = [int(sys.stdin.readline()) for _ in range(N)]
weight.sort(reverse = True) # 내림차순으로 정렬

result = []

for i in range(N):
    heapq.heappush(result, -weight[i] * (i + 1))

print(-heapq.heappop(result))
    heappop()はO(logn)O(logn)O(logn)O(logn)O(logn)の時間的複雑さを有し、
    print(-result[0]) # 최대힙의 루트값
    に変更すると、
    になります.
    TCPServer+StreamRequestHandlerネットワークプログラミング
    スレッド同期コンポーネント