1966号プリンタキュー

質問元:https://www.acmicpc.net/problem/1966
かなり時間のかかる問題.これは、indexに基づいて新しい配列を簡単に作成し、円形のキューで処理するだけで、この問題を解決することができます.私たちはある規則、公式を見つけて、よりクールで、より効果的な方法で追求しようとしているので、これは長引く問題です.

イニシアチブ

num[0]の後ろにもっと大きなものがあると出力できないと思います.num[0]より大きい値をpopすればいいです.このときnum[0]より大きい最大インデックスが最後に出力されてからarr[0]と同じ値の要素の出力が開始されます...

import sys

T = int(sys.stdin.readline().rstrip("\n"))

for _ in range(T) :
    N,M = list(map(int,sys.stdin.readline().rstrip("\n").split()))
    num = list(map(int,sys.stdin.readline().rstrip("\n").split()))
    target, result = num[M], 0
    min_n,idx = float('inf'), 0
    same_i = []
    
    #IN Bigger than target, min is last pop
    #After that same with target num pop
    for n in range(N) :
        if num[n] > target :
            if min_n>num[n] :
                min_n = num[n]
                idx = n
            elif min_n == num[n] :
                idx = max(idx,n)
            result+=1
        elif n!=M and (num[n]==target) :
            same_i.append(n)
    
    for m in same_i :
        if idx<M :
            if (idx<m) and (m<M) : result+=1
        if M < idx :
            if not (M<m and m<idx) : result+=1
    print(result+1)

結果は失敗!

円形キューのように実装

import sys
from collections import deque

T = int(sys.stdin.readline().rstrip("\n"))

for _ in range(T) :
    N, M = list(map(int,sys.stdin.readline().rstrip("\n").split()))
    num = list(map(int,sys.stdin.readline().rstrip("\n").split()))
    result = 0
    new = deque([])
    for i,n in enumerate(num) :
        new.append([i,n])
        
    while True:
        if new[0][1] == max(new, key = lambda x: x[1])[1] :
            if new[0][0] == M :
                break
            new.popleft()
            result+=1
        else :
            new.append(new.popleft())
    print(result+1)

ブルートフォース?

うん。以前教授はwhile True Moonは無限反復だからよくないと言っていましただから私はただ解決したいだけです。これから機会があればもう少し発展します疲れたから (listのpop(0)を書くと時間の複雑さが少し大きくなるのでdequeを書きましたがlistの方が早い…?)

lisiant01 iougou03