欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

F - Feel Good Gym - 101334F 经典思维(前缀和)

程序员文章站 2022-03-12 16:33:32
...

F - Feel Good Gym - 101334F 经典思维(前缀和)



题意:

给出正整数的数组,让你求出此数组某一个区间的和乘以区间内的最小值

题解:

求出前缀和,然后求出每一个数比这个数小的左右端点

这里注意一个优化:就可以跳着走,当一个数比他大的时候,然后就可以跳到比他大的数的端点去


#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;
}