Feel Good POJ – 2796(单调栈应用三)

题目链接:https://cn.vjudge.net/problem/POJ-2796#author=Tiw_Air_OAO
题目大意:题给你一个非负整数数组,定义某个区间的参考值为:区间所有元素的和乘以区间最小元素。求该数组中的最大参考值以及对应的区间。
比如说有6个数3 1 6 4 5 2
最大参考值为6,4,5组成的区间,区间最小值为4,参考值为4*(6+5+4)=60
数据范围1<=n<=100000;(转自题目评论区)

解题思路:
首先要整一个前缀和,然后我们要求每一个数以它为最小值的最大的区间,这就要用到单调栈了
以样例 3(1,1) 1(2,2) 6(3,3) 4(4,4) 5(5,5) 2(6,6) 为例(括号中是以这个值为最小值的区间)
首先将 3(1,1) 入栈
然后判断 1(2,2) ,由于1比3小所以将 1(2,2) 与 3(2,2)合并,也就是将3(2,2)出栈,将1(2,2)改为1(1,2)并入栈,这样就完成了区间的向左延申,出栈的时候要判断一下以1为最小值的结果。
然后判断 6(3,3) ,由于6比3大,直接入栈
然后是 4(4,4),5(5,5)都与之前1(2,2)的入栈相似
最后是2(6,6)的入栈了,这时候栈中还有1(1,2),6(3,4),5(5,5)三个区间,由于2比他们都小,所以要将他们依次出栈,出栈时计算的右端点都是5(5,5)中的右端点5,原因是显而易见的。
最后不要忘记把栈中元素排空

代码

#include <iostream>
#include <stack>
#include <cstdio>
using namespace std;

struct node
{
    long long data,l,r;
};
long long a[100010],sum[100010];
stack<node>q;
int main()
{
    //ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        sum[i]=a[i]+sum[i-1];
    }
    long long ans=-1,ansl,ansr;
    node ddd;
    int rr;
    for(int i=1; i<=n; i++)
    {
        ddd.l=i;
        ddd.r=i;
        ddd.data=a[i];
        if(q.empty())
        {
            q.push(ddd);
        }
        else
        {
            rr=q.top().r;
            while(!q.empty()&&q.top().data>ddd.data)
            {
                ddd.l=q.top().l;
                if(ans<q.top().data*(sum[rr]-sum[q.top().l-1]))
                {
                    ans=q.top().data*(sum[rr]-sum[q.top().l-1]);
                    ansl=q.top().l;
                    ansr=rr;
                }
                q.pop();
            }
            q.push(ddd);
        }
    }
    rr=q.top().r;
    while(!q.empty())
    {
        if(ans<q.top().data*(sum[rr]-sum[q.top().l-1]))
        {
            ans=q.top().data*(sum[rr]-sum[q.top().l-1]);
            ansl=q.top().l;
            ansr=rr;
        }
        q.pop();
    }
    cout<<ans<<endl;
    cout<<ansl<<" "<<ansr<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注