The Preliminary Contest for ICPC China Nanchang National Invitational I.Max answer单调栈

佚名 5年前 (2019-04-21) 随笔 987人围观抢沙发百度已收录

题面

题意:一个5e5的数组,定义一个区间的值为这个区间的和*这个区间的最小值,注意数组值有负数有正数,求所有区间中最大的值

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题解:如果全是正数,那就是原题 POJ2796 单调栈做一下就ok

我们现在有负数,考虑这段区间,他的和必须是负数,由于导致和为负数,最小值一定也是负数,

那对于这样一个和为负的区间进行扩展的时候,遇见下一个数,是负数,我们一定会扩展,无论这个负数大小

遇见下一个是正数,如果和没有变正,那就可以继续扩展下去(不更新答案罢了)

所以我们对于那些和为负的区间,单独统计一下答案就好了,顺路就统计这个区间的最小值,因为一旦抛弃她就再也不会回头了!

所以压根不用线段树 ST表之类的,对于负数的和,整体按POJ2796做的取个min,就行了.复杂度O(n)

 1 #include<bits/stdc++.h>
 2 #define lld long long 
 3 #define N 500050
 4 using namespace std;
 5 int n;
 6 lld a[N],sum[N],x[N],xx[N];
 7 lld L[N],R[N],ansv,ans1;
 8 int main ()
 9 {
10     scanf("%d", &n);
11     for (int i=1;i<=n;i++)
12     {
13         scanf("%lld",&x[i]);
14         xx[i]=x[i];
15     }
16     lld ww=xx[1],minx=xx[1];
17     for (int i=1;i<=n;i++) 
18     {
19         if (xx[i-1]<0) 
20         {
21               minx=min(minx,xx[i]);
22             xx[i]+=xx[i-1]; 
23         }else 
24         {
25             xx[i]+=0;
26             minx=1e18;
27         }
28         if (xx[i]<ww) 
29         {
30             ww=xx[i];
31             ansv=minx;
32         }
33     }
34     if (ww<0) ans1=ww*ansv;
35     for (int i=1;i<=n;i++) a[i]=x[i];
36     for (int i=1;i<=n;i++) 
37     {
38         sum[i]=sum[i-1]+a[i];
39         L[i]=R[i]=i;
40      }
41      a[0]=a[n+1]=-1e9;
42     for (int i=1;i<=n;i++) 
43         while(a[i]<=a[L[i]-1]) L[i]=L[L[i]-1];
44     for (int i=n;i>=1;i--)
45         while(a[i]<=a[R[i]+1]) R[i]=R[R[i]+1];
46     lld ans=-1e18,l,r;
47     for (int i=1;i<=n;i++)
48     {
49         lld T=a[i]*(sum[R[i]]-sum[L[i]-1]);
50         if(ans<T) ans=T,l=L[i],r=R[i];
51     }    
52     cout<<max(ans,ans1)<<endl;
53 }