[python]白準1966プリンタキュー(Deque)
11853 ワード
📌 質問する
ご存じのように、プリンタでは、印刷するドキュメントを印刷コマンドを受信した順序、すなわち、要求されたドキュメントを先に印刷します.複数の文書がキュー資料構造に積み重ねられている場合、FIFO-Firstの第1の出力に従って印刷されます.しかし、尚根は、以下の条件で印刷する新しいプリンタ内部ソフトウェアを開発した.
現在のキュー内のドキュメントの数と重要性を指定したときに、どのドキュメントが何回目に印刷されたかを特定します.例えば、上記の例では、Cドキュメントが1位、Aドキュメントが3位となっている.
入力
最初の行は、テスト・インスタンスの数を示します.各テストボックスは2行で構成されています.
テストケースの最初の行には、ドキュメントの数N(1≦N≦100)と、現在のQueueで何位にランクされているかを示す整数M(0≦M
しゅつりょく
各テスト例について、ドキュメントの数回目の印刷を出力します.
入力例
3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1
翻訳がうまくいかないので、理解を助けるために絵を描きました.優先順位キューによっては、何回目の印刷赤を求めればよいのです.
サンプル出力
1
2
5
📌 に答える
コード#コード#
import sys
from collections import deque
input = sys.stdin.readline
tc = int(input())
for _ in range(tc):
n, idx = map(int, input().split())
q = deque(map(int, input().split()))
idxq = deque(range(0, n))
cnt = 0
while q:
if q[0] == max(q):
cnt += 1
q.popleft()
if idxq.popleft() == idx:
print(cnt)
break
else:
q.rotate(-1)
idxq.rotate(-1)データ構造の説明
q.rotate(-1)を使用してq.append(q.popleft()ロールを実行できます.rotate(-1)は円形キューが反時計回りに1マス回転し,rotate(1)が時計回りに1マス回転すると考えられる.そのため、(-1)を回転させると、一番前に飛び出して最後まで押します.
問題において所望の機能を実現した.ただそうすると、0番目のインデックスに含まれていた値が何なのかが失われます.問題は「初期状態の0番目のインデックスにはいくつ目のpopが含まれている」ため、回転時に初期状態のインデックス情報を失うことはできません.
そこで、インデックス情報を含むdequeが新しく作成されました.idxq=deque(range(0,n))!qのインデックスはidxqの値です.qが回転するとidxqも回転し,初期状態のインデックスと値を共に移動させる.
操作の説明
キューの一番前の値が現在のキューで一番大きい場合にポップアップされるので、q[0]とmax(q)を比較します.
同じ場合、pop個数を表すcntは1,pop増加する.もちろんidxqでもpopは一緒ですが、このpop値が私たちが注目しているインデックスと同じであれば、実行を終了し、出力cntは何回目のpopです.
違うと、キューを回します(-1).
実行手順は以下のとおりです.
> 1
6 0
1 1 9 1 1 1
[1, 1, 9, 1, 1, 1]
[1, 9, 1, 1, 1, 1]
[9, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1]
[1, 1, 1, 1]
[1, 1, 1]
[1, 1]
break> 1
4 2
1 2 3 4
[1, 2, 3, 4]
[2, 3, 4, 1]
[3, 4, 1, 2]
[4, 1, 2, 3]
[1, 2, 3]
[2, 3, 1]
[3, 1, 2]
breakReference
この問題について([python]白準1966プリンタキュー(Deque)), 我々は、より多くの情報をここで見つけました https://velog.io/@hygge/Python-백준-1966-프린터-큐-dequeテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol