51nod——2476 小b和序列（预处理思维）

　　对于每一个元素，预处理出它作为最小值，两边可以作用到的最大位置。比如下标∈[0,8]的这个数组：1 8 6 2 5 4 3 8 7，1可以作用到所有区间，2可以作用到区间[1,8]，第一个8可以作用到[1,7]。也就是说从两边分别找到第一个大于等于这个元素的位置，然后标记，其实就是找最宽的区间长度。可能左边更宽也可能右边更宽，对所有元素的max(a[i]*(i-l[i])),a[i]*(r[i]-i)) 求max就是答案了。

 #include <bits/stdc++.h>

 using namespace std;

 #define maxn 50050

 int a[maxn],l[maxn],r[maxn];

 int main(){

     std::ios::sync_with_stdio();

     cin.tie();

     int n; cin>>n;

     for(int i=;i<n;i++) cin>>a[i];

     for(int i=;i<n;i++){//预处理 找到可以以a[i]为最小值的区间

         int ll=,rr=n-;

         while(a[ll]<a[i]) ll++;

         l[i]=ll;

         while(a[rr]<a[i]) rr--;

         r[i]=rr;

     }

     int maxx=;

     for(int i=;i<n;i++)

         maxx=max(max(maxx,a[i]*(i-l[i])),a[i]*(r[i]-i));

     cout<<maxx<<endl;

     return ;

 }

巴特西

51nod——2476 小b和序列（预处理思维）

最新文章

热门文章

巴特西

51nod——2476 小b和序列（预处理 思维）

最新文章

热门文章

51nod——2476 小b和序列（预处理思维）