[TIOJ] 1721. 山上的風景

題目連結:http://tioj.infor.org/problems/1721
往右往左各分別維護一個遞減的stack,而若是塞入的東西比較大,則就把比他小的全部pop掉,同時也保證他們都只能看到這裡。
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef pair<int,int> PII;
#define FF first
#define SS second
const int N = 100000 + 5;

int arr[N], ans[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	while(cin>>n){
		for(int i=0;i<n;i++) cin>>arr[i];
		stack<PII> ss;
		for(int i=0;i<n;i++){
			while(!ss.empty() and ss.top().FF <= arr[i]){
				ans[ss.top().SS] = i-ss.top().SS+1;
				ss.pop();
			}
			ss.push({arr[i], i});
		}
		while(!ss.empty()){
			ans[ss.top().SS] = n-ss.top().SS;
			ss.pop();
		}
		for(int i=n-1;i>=0;i--){
			while(!ss.empty() and ss.top().FF <= arr[i]){
				ans[ss.top().SS] += ss.top().SS-i;
				ss.pop();
			}
			ss.push({arr[i], i});
		}
		while(!ss.empty()){
			ans[ss.top().SS] += ss.top().SS;
			ss.pop();
		}
		for(int i=0;i<n;i++) cout<<ans[i]<<" \n"[i==n-1];
	}
	return 0;
}

留言

這個網誌中的熱門文章

[NPSC] 2009初賽 E. 檸檬汽水傳說

[TIOJ] 1902. 「殿仁.王,不認識,誰啊?」,然後他就死了……

[AtCoder] [經典競程 90 題] 024 - Select +/- One(★2)