1715カードソート
3884 ワード
質問する
きちんとした数字カードが2束あると言ってください.1束あたりのカードの数をA、Bと言います.普通は2束を合わせて1つ作って、A+Bの比較をします.例えば、20枚のデジタルカードと30枚のデジタルカードの組み合わせを50回比較する必要がある.
多くのデジタルカードが机の上に縛られている.2束に分けると、選択順によって比較回数が大きく異なります.例えば、10枚、20枚、40枚のギフトバッグがあれば、10枚と20枚のギフトバッグを合わせ、30枚のギフトバッグと40枚のギフトバッグを合わせて(10+20)+(30+40)=100回の比較が必要です.しかし10枚と40枚を合わせた後、50枚と20枚を加えると(10+40)+(50+20)=120回の比較が必要なので非効率的な方法です.
N個のデジタルカードグループの各時間を指定すると、少なくとも何回の比較が必要かを求めるプログラムを作成します.
入力
1行目はNです.(1≦N≦100000)は、N行においてデジタルカード群の各サイズを与える.デジタルカードグループのサイズは1000以下の整数です.
しゅつりょく
1行目に最小比較回数を出力します.
#解答
[原句]値段が一番安いために、大きいほど触らないほうがいいです.
1.最低2個の紙を混ぜ合わせてカードリストに入れる
2.その中から最も少ない2つの重複を選択します.import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline
import heapq
N = int(input())
cardlist=[]
for _ in range(N):
cardlist.append(int(input()))
cardlist = sorted(cardlist) # 입력 받고 정렬 한번 한다.
count =0
while cardlist: # cardlist가 빌때까지!
try: # heapqpop으로 뽑으면 가장 작은 값 두개가 뽑아진다.
mix = heapq.heappop(cardlist)+heapq.heappop(cardlist)
count += mix
# 가장 얇은 카드 뭉치의 합은 묶여서 다시 넣어진다.
heapq.heappush(cardlist,mix)
except: # 두개가 못뽑아진다 == 한개 남았을 때는 끝난 거라서 출력하면서 끝
print(count)
Reference
この問題について(1715カードソート), 我々は、より多くの情報をここで見つけました
https://velog.io/@bbnerino/1715-카드정렬
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
1行目はNです.(1≦N≦100000)は、N行においてデジタルカード群の各サイズを与える.デジタルカードグループのサイズは1000以下の整数です.
しゅつりょく
1行目に最小比較回数を出力します.
#解答
[原句]値段が一番安いために、大きいほど触らないほうがいいです.
1.最低2個の紙を混ぜ合わせてカードリストに入れる
2.その中から最も少ない2つの重複を選択します.import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline
import heapq
N = int(input())
cardlist=[]
for _ in range(N):
cardlist.append(int(input()))
cardlist = sorted(cardlist) # 입력 받고 정렬 한번 한다.
count =0
while cardlist: # cardlist가 빌때까지!
try: # heapqpop으로 뽑으면 가장 작은 값 두개가 뽑아진다.
mix = heapq.heappop(cardlist)+heapq.heappop(cardlist)
count += mix
# 가장 얇은 카드 뭉치의 합은 묶여서 다시 넣어진다.
heapq.heappush(cardlist,mix)
except: # 두개가 못뽑아진다 == 한개 남았을 때는 끝난 거라서 출력하면서 끝
print(count)
Reference
この問題について(1715カードソート), 我々は、より多くの情報をここで見つけました
https://velog.io/@bbnerino/1715-카드정렬
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline
import heapq
N = int(input())
cardlist=[]
for _ in range(N):
cardlist.append(int(input()))
cardlist = sorted(cardlist) # 입력 받고 정렬 한번 한다.
count =0
while cardlist: # cardlist가 빌때까지!
try: # heapqpop으로 뽑으면 가장 작은 값 두개가 뽑아진다.
mix = heapq.heappop(cardlist)+heapq.heappop(cardlist)
count += mix
# 가장 얇은 카드 뭉치의 합은 묶여서 다시 넣어진다.
heapq.heappush(cardlist,mix)
except: # 두개가 못뽑아진다 == 한개 남았을 때는 끝난 거라서 출력하면서 끝
print(count)
Reference
この問題について(1715カードソート), 我々は、より多くの情報をここで見つけました https://velog.io/@bbnerino/1715-카드정렬テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol