标签：ch const int pop 迈克 ans define

题目描述

有n只熊。他们站成一排队伍，从左到右依次1到n编号。第i只熊的高度是a[i]。

一组熊指的队伍中连续的一个子段。组的大小就是熊的数目。而组的力量就是这一组熊中最小的高度。

迈克想知道对于所有的组大小为x（1 ≤ x ≤ n）的，最大力量是多少。

 

题解：

这题很妙的是：我们以第i个熊作为中心，算出以他为最小的值的那段最大区间

所以就是以第i个熊为中心，找出左右第一个小于他的L,R,这样符合的区间就是[L+1,R-1]

那么这就意味这在[L+1,R-1]里的任何包含 i 的段的最小值就是a[i]

所有我们可以先单调栈求出L,R,再统计答案

但是还有要注意的一点：比如答案一定是单调递减,所以遇到不是单调递减的就要让他

最后一步要: 

for(int i=n;i;i--) ans[i]=max(ans[i],ans[i+1]);

ans[i+1]满足的，对于ans[i]一定满足，但是一开算出的ans[i]是有可能小于ans[i+1]的，不符合

因为长度越长，对于一组熊的最小高度一定越小，而最后的ans(最大力量也会越小)也会小

 

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back   //vector函数
#define popb pop_back  //vector函数
#define fi first
#define se second
const int N=2e5+10;
//const int M=;
//const int inf=0x3f3f3f3f;     //一般为int赋最大值,不用于memset中
//const ll INF=0x3ffffffffffff; //一般为ll赋最大值,不用于memset中
int T,n,a[N],l[N],r[N],ans[N];
stack<int> s;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
int main()
{
//    freopen("","r",stdin);
//    freopen("","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++)
    {
        while(!s.empty()&&a[s.top()]>=a[i]) s.pop();
        if(s.empty()) l[i]=0;
        else l[i]=s.top();
        s.push(i);
    }
    while(!s.empty()) s.pop();
    for(int i=n;i;i--)
    {
        while(!s.empty()&&a[s.top()]>=a[i]) s.pop();
        if(s.empty()) r[i]=n+1;
        else r[i]=s.top();
        s.push(i);
    }
    for(int i=1;i<=n;i++)
    {
        int len=r[i]-l[i]-1; //(r[i]-1)-(l[i]+1)-1
        ans[len]=max(ans[len],a[i]);
    }
    for(int i=n;i;i--) ans[i]=max(ans[i],ans[i+1]);
    for(int i=1;i<=n;i++) printf("%d ",ans[i]);
    return 0;
}

 

标签：ch,const,int,pop,迈克,ans,define
From： https://www.cnblogs.com/Willette/p/17043461.html