F - Feel Good Gym - 101334F 经典思维(前缀和)
程序员文章站
2022-03-12 16:33:32
...
题意:
给出正整数的数组,让你求出此数组某一个区间的和乘以区间内的最小值
题解:
求出前缀和,然后求出每一个数比这个数小的左右端点
这里注意一个优化:就可以跳着走,当一个数比他大的时候,然后就可以跳到比他大的数的端点去
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define LL long long
#define MAXN 100005
int L[MAXN],R[MAXN];
int a[MAXN];
LL sum[MAXN];
int main()
{
int n;
//freopen("in.txt","r",stdin);
freopen("feelgood.in","r",stdin);
freopen("feelgood.out","w",stdout);
while(scanf("%d",&n)!=EOF)
{
sum[0]=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
L[0]=1;
R[n]=n+1;
int i,j;
for(i=2;i<=n;i++){
for(j=i-1;j>=1;){
if(a[j]<a[i]){ L[i]=j;break;}
else j=L[j];
}
}
for(i=n-1;i>=1;i--){
for(j=i+1;j<=n;){
if(a[j]<a[i]){ R[i]=j;break;}
else j=R[j];
}
if(j>n)
R[i]=n+1;
}
LL ans=-1,temp;
int l,r;
for(int i=1;i<=n;i++){
temp=a[i]*(sum[R[i]-1]-sum[L[i]]);
if(ans<temp)
ans=temp,l=L[i]+1,r=R[i]-1;
}
printf("%lld\n%d %d\n",ans,l,r);
}
return 0;
}
下一篇: 一个有意思的Java集合类