[Sart]Boj 1015:数列ソート

1907 ワード
テキストリンク

[Sart]Boj 1015:数列ソート


Link: https://www.acmicpc.net/problem/1015

質問する


P[0], P[1], ...., P［N−1］は0からN−1(含む)まで一度の数列である.数列Pは長さNの配列Aに適用され、長さNの配列Bとなる.適用できる方法はB[P[i]=A[i]です.
配列Aが与えられると、適用配列Pの結果が降順でない配列を検索するプログラムを作成します.雨量降順とは、各元素が前の元素より大きいか等しいかを指す.そのような数列が複数ある場合、出力は辞書順にリードします.

入力


第1行は、配列AのサイズNを与える.2行目では、配列Aの要素はゼロから順に与えられる.Nは50以下の自然数であり、配列された要素は1000以下の自然数である.

しゅつりょく


1行目は降雨順に生成された数列Pを出力する.

I/O例



問題を理解する

  • 入力値は、リストAである.
  • 我々が求めているのはPの数列であり,BはPを求める過程であり,理解が容易である.
  • BリストはAの値ソートに等しい.
  • A[i]=B[P[i]はPを求める式であり、簡単に言えば、i第Aの値は「i第Pの値」第Bに等しい.すなわち、ソートされたリストBのインデックスが、リストAにおいて値の順に同じようにリストされている場合、Pの値となる.
    • 次のコードを見て、コメントを参考にして、理解しやすくなります.

    Code | Python

    import sys
si = sys.stdin.readline
N = int(si())
A = list(map(int,si().split()))

sortList = [[] for _ in range(N)]
#입력 받은 리스트 A의 값과 그 인덱스를 함께 저장해준다.
for i in range(N):
    sortList[i].append(i)
    sortList[i].append(A[i])

#A의 값을 기준으로 정렬해준다.
sortList.sort(key = lambda x:x[1])

#정렬된 리스트에 다시 한번 현재 인덱스(P값)를 append 해준다.
for i in range(N):
    sortList[i].append(i)

#가장 처음 리스트 A의 인덱스 순서대로 정렬 후, 마지막에 구한 P값을 출력한다.
for x in sorted(sortList,key = lambda x:x[0]):
    print(x[2], end = ' ')

    Screenshot | Output



    より良いコード

    import sys
si = sys.stdin.readline
n = int(si())
A = list(map(int, sys.stdin.readline().split()))
B = [(x, i) for i, x in enumerate(a)]
B.sort()
P = [0 for _ in range(n)]
for i in range(n):
    P[B[i][1]] = i
for i in range(n):
    print(P[i], ' ')
    [プログラマレベル1]-区切られた数値配列
    UDP通信受信側は、2次元配列を受信し、内容は0と1