程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Codeforces 547B Mike and Feet(單調棧)

Codeforces 547B Mike and Feet(單調棧)

編輯:關於C++
B. Mike and Feet time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Mike is the president of country What-The-Fatherland. There are n bears living in this country besides Mike. All of them are standing in a line and they are numbered from 1 to n from left to right. i-th bear is exactly ai feet high.

\

A group of bears is a non-empty contiguous segment of the line. The size of a group is the number of bears in that group. The strengthof a group is the minimum height of the bear in that group.

Mike is a curious to know for each x such that 1 ≤ x ≤ n the maximum strength among all groups of size x.

Input

The first line of input contains integer n (1 ≤ n ≤ 2 × 105), the number of bears.

The second line contains n integers separated by space, a1, a2, ..., an (1 ≤ ai ≤ 109), heights of bears.

Output

Print n integers in one line. For each x from 1 to n, print the maximum strength among all groups of size x.

Sample test(s) input
10
1 2 3 4 5 4 3 2 1 6
output

6 4 4 3 3 2 2 1 1 1

 

 

 

題目大意:

給出n個數,這n個數在區間長度為i(1~n)的時候可以分割成一些區間,這每個區間都會有一個最小值,在同樣長度的這些區間的最小值中,輸出最大值。
思路:利用單調棧,保持棧內單調遞增。

單調棧:單調棧是以某一個值為最大(最小)值,向兩個方向進行延伸,如果兩邊的數比他大(小),就進行延伸。並且利用棧可以使時間復雜度控制在O(n)。

#include #include #include #include #include #define LL __int64 using namespace std; struct node{ LL num,pre,next; }; //代表數字,前驅有幾個,後繼有幾個。 LL max(LL a,LL b){ return a>b?a:b; } LL a[200005],ans[200005]; int main() { LL n,i,j; while(scanf(%I64d,&n)!=EOF) { stackQ; node tmp; memset(ans,0,sizeof(ans)); //ans數組記錄i范圍時的最大數字。 for(i=1;i<=n;i++) { scanf(%I64d,&a[i]); } tmp.num=a[1]; tmp.pre=tmp.next=1; Q.push(tmp); for(i=2;i<=n;i++) { node tmp1; tmp1.num=a[i]; tmp1.pre=tmp1.next=1; while(!Q.empty()&&Q.top().num>=tmp1.num) { tmp=Q.top(); Q.pop(); if(!Q.empty()) Q.top().next+=tmp.next; tmp1.pre+=tmp.pre; LL l=tmp.pre+tmp.next-1; //記錄長度 ans[l]=max(ans[l],tmp.num); //比較長度為l 的ans大小。 } Q.push(tmp1); } while(!Q.empty()) { tmp=Q.top(); Q.pop(); if(!Q.empty()) Q.top().next+=tmp.next; LL l=tmp.pre+tmp.next-1; ans[l]=max(ans[l],tmp.num); } for(i=n-1;i>=1;i--) ans[i]=max(ans[i],ans[i+1]); //最後還要更新一下,可能中間有些長度沒有被更新到。而且可以斷定ans[i+1]>ans[i]一定成立。 for(i=1;i

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved