POJ 3250

POJ 3250

題敘

https://vjudge.net/problem/POJ-3250
可見杆問題
給一群杆子的高度,求在每根杆子上向右看能看到的杆子數量總和
定義能看到是你所在的桿杆和該桿杆之間的所有桿杆高度都小於你所在的桿杆的高度

想法

觀察能看到其他杆子的集合所形成的序列可以發現是呈現 遞減 的狀態
因此我們只要能維護一個嚴格遞減的序列,剩下的就必定會是能看到其他人的杆子
因為這裡的狀態是先進後出,跟stack一樣,所以選擇stack
每次將stack內所剩餘的元素數量加總即可求解

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//By Koios1143
#include<iostream>
#include<stack>
#define int long long
#define pii pair<int,int>
using namespace std;
int n,m,ans=0;
stack<int> st;
signed main(){
while(cin>>n){
ans=0;
while(!st.empty()) st.pop();
while(n--){
cin>>m;
while(!st.empty() && m>=st.top())
st.pop();
ans+=st.size();
st.push(m);
}
cout<<ans<<'\n';
}
return 0;
}

複雜度

掃過一次字串即可,複雜度 O(len(m))
總複雜度 O(nlen(m))

Gitalk 載入中…