首页 > 代码库 > Gym 101334F Feel Good

Gym 101334F Feel Good

2024-10-01 13:06:02   218人阅读

题意：

给定一串数，求一个区间，使得该区间的所有数之和乘以该区间内最小的数的乘积最大。

分析：

每一个元素都有可能为该区间最小值，所以我们往该元素的左右方向扩展，越大越好。但是扩展的时候如果逐个遍历肯定会超时，那么这个地方需要一个优化。如果往左遇到的是比自己要大的元素，可以直接跳到这个大的元素对应的比它小的坐标数。求出区间后，利用前缀和即可快速求出答案。

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=100000+5;ll a[maxn],s[maxn];int l[maxn],r[maxn];int main(){    freopen("feelgood.in","r",stdin);    freopen("feelgood.out","w",stdout);    int n;    scanf("%d",&n);    for(int i=1; i<=n; i++)    {        scanf("%I64d",&a[i]);        s[i]=s[i-1]+a[i];    }    for(int i=1; i<=n; i++)    {        int j=i-1;        while(1)        {            if(a[j]<a[i] || j==0)            {                l[i]=j;                break;            }            else                j=l[j];        }    }    for(int i=n; i>=1; i--)    {        int j=i+1;        while(1)        {            if(a[j]<a[i] || j==n+1)            {                r[i]=j;                break;            }            else                j=r[j];        }    }    int pos=1;    ll ans=0;    for(int i=1;i<=n;i++)    {        ll temp=a[i]*(s[r[i]-1]-s[l[i]]);        if(ans<temp)        {            ans=temp;            pos=i;        }    }    printf("%I64d\n",ans);    printf("%d %d\n",l[pos]+1,r[pos]-1);    return 0;}

 

Gym 101334F Feel Good


联系
我们