当前位置：首页 > news >正文

UVA1619 Feel Good（链表+前缀和）

news 来源：原创 2024/5/21 0:31:30

传送门

在这里插入图片描述
1.题目大意：给出一个长度为n的正整数序列a，求一段连续的子序列a₁,a₂,…,a_n使得(a₁+a₂+…+a_n)*min{a₁,a₂,…,a_n}尽量大。如果有多解输出长度最短且最左边的解

2.第一眼想到了尺取，但是感觉这样O(n²)要超时。这里不但区间长度会约束答案，而且区间最小值也会约束答案，没想到怎么实现tcl

3.实际上是链表的思想，对于每个数，我们以它为这个区间的最小值，那么看看这个数向两边能拓展的最大区间是多大——该区间内这个数为最小值，这样之后如果我们暴力求这段区间，肯定超时，因此这里用到了单调栈和链表的思想：在扫描过程中维护一个向前延伸的最大位置，如果前面一个元素不比它小，那么前面一个元素能延伸到的位置，当前元素也可以延伸到，然后类似链表往前延伸，右边同理，这样的话时间复杂度实际上只有O(n)

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

int a[maxn],L[maxn],R[maxn];
ll sum[maxn];  //1e5个1e6数会爆int

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,kase=0;
    while(cin>>n){
        for(int i=1;i<=n;i++){
            cin>>a[i];
            sum[i]=sum[i-1]+a[i];
            L[i]=R[i]=i;  //初始设置向右向左扩展的长度均为0
        }
        a[0]=a[n+1]=-1;  //因为序列都是正数，因此取
        for(int i=1;i<=n;i++){
            while(a[i]<=a[L[i]-1]) L[i]=L[L[i]-1];  //细细体会
        }
        for(int i=n;i>=1;i--){
            while(a[i]<=a[R[i]+1]) R[i]=R[R[i]+1];
        }
        ll ans=1LL*a[1]*a[1],l=1,r=1;  //ans,l,r都设置为第一组数据，否则会wa
        for(int i=1;i<=n;i++){
            ll res=(sum[R[i]]-sum[L[i]-1])*a[i];
            if(res>ans || (res==ans && (R[i]-L[i])<(r-l))){ //只需设置>就能保住是最左边，第二个判断条件为长度最短
                ans=res;
                l=L[i],r=R[i];
            }
        }
        if(kase++) cout<<endl;  //相邻输出有多余的回车，首尾无
        cout<<ans<<endl;
        cout<<l<<" "<<r<<endl;
    }
    return 0;
}