BOJ 3015オアシス再結合

質問する

BOJ 3015オアシス再結合
金色I|白準3015|Python 3 Python草

アルゴリズム#アルゴリズム#

意見の食い違いが多いので、厄介な問題です.アルゴリズムのコアは、鍵ごとに大きく3つのブランチに分けることができる.小さい、大きい、同じ状況.このとき,時間的複雑さを低減するためにスタックを用いる.
特定のインデックス内のキーについて、その位置から前向きな人を計算します.
どんな二人にも相手を見せるためには、彼ら二人の間には彼らより背の高い人がいるはずがない.現在のスタックにtopより大きいキーがある場合、その後の人は現在のスタックのtop値を絶対に見ることができません.すなわち、現在のスタックのtop(pop)を破棄する.
現在のスタックにtop未満のキーがある場合、この値はスタックにプッシュされ、候補群に追加されます.
stackにはキーだけでなく、キーを表示できる人数も含まれます.
スタックの上部の人の身長がhth thtなら、
現在のステップのキーがhch chcである場合、
ht>hch t>h cht>hcであれば、hch chcの後の人はhth thtを見ることができないので、hth thtを捨てる前にcountを増やし、ht=hch t=hcht=hcであれば、現在hth thtを見ることができる人はhch chcを見ることもできるので、現在hchcを見ることができる人の数はnowcountに増やすことができる.
htcount増加する.

コード#コード#

import sys

input = sys.stdin.readline

N = int(input())
heights = [int(input()) for _ in range(N)]

count = 0
stack = []

for height in heights:
    nowcount = 1
    while stack:
        if height >= stack[-1][0]:
            count += stack[-1][1]
			
            # 현재 스택의 top과 키가 같다면
            if height == stack[-1][0]:
            	# 볼 수 있는 사람 수를 더해준다
                nowcount += stack[-1][1]
			
            # 더 이상 stack의 top을 볼 수 있는 사람이 없으므로
            # 스택에서 버린다.
            stack.pop()

        else:
            # 서로 볼 수 있는 쌍
            count += 1
            break
	
    # 스택에 해당 키를 넣는다
    # 이때, 현재 사람을 볼 수 있는 카운트를 추가
    stack.append((height, nowcount))

print(count)

結果

難題のようです.(すぐにプレイ5にアップしても)