白駿10989号:数列3

3295 ワード
python ps Counting Sort Sort テキストリンク
白駿10989号:数列3

アイデア


入力された個数は千万個あります.sort()だけを考えていると、メモリがオーバーします.しかし、数字の最高価格は10000です.これをよく利用しましょう.
10001個の配列を作成し、0で埋めます.aという名前の数字を入力すると、1番目のインデックスに値を追加します.
0より大きい値が格納されている場合は、対応するインデックスが入力されている数値を示します.保存した値に従って複数回出力します.

コード#コード#

import sys
input = sys.stdin.readline
N = int(input().rstrip())
cSort = [0]*10001

while N > 0:
    num = int(input().rstrip())
    cSort[num] += 1
    N -= 1

for i in range(10001):
    if cSort[i] > 0:
        cnt = cSort[i]
        while cnt > 0:
            print(i)
            cnt -= 1

おしゃべり


通常の方法で入力するとタイムアウトします.だからsys.stdin.readlineで入力を受信します.
ubuntu上でNDK 21に基づいてffmpeg 4をコンパイルする.2.2
HDU-4973(線分ツリー+二分)