自动搬运

查看原文

来自洛谷，原作者为

	karma **

搬运于2025-08-24 21:40:08，当前版本为作者最后更新于2017-11-08 20:04:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看了楼下的3篇题解.感觉还是说的不明白.具体遇到题该怎么分析,并没有指出.所以写这篇题解作为补充.此题正解为单调递增栈.

分析:

为什么是单调递增栈?

此题要求维护区间最小值.

当遍历到后面的元素时,发现此时的元素比之前的最小值要小.意味着之前的最小值已经失效.之后不会再是最小值.所以可以找到它管辖的区间(即在这个区间中,它是最小值)的长度,进而算出区间的美丽值.计算后弹出栈

当遍历到后面的元素时,发现此时的元素比之前的最小值要大.故它不可能成为该区间的最小值.可以保留下来.可能从它开始有一段区间受它管辖.(管辖意义同上).使它进栈.

步骤:

此题单调栈要用结构体保存它的值和下标.方便计算它管辖区间的长度.当之后有元素比它小时.它管辖的区间长度即此时的下标减去它之前的一个最小值的下标减1.(原因:不算这个位置和前一个最小值的位置).

最后还要遍历栈.此时每一个元素的管辖区间的右端点均为N.故区间长度为N减该元素进栈时的下标.

代码如下:

#include<cstdio>
#define maxn 2000005
struct node{
    long long idx,val;
    //dix为下标,val为值 
}a[maxn],st[maxn];
//st[]为单调递增栈 
//其实a[]没必要用结构体 
int N,top;
long long ans;
long long Max(long long x,long long y){return x>y?x:y;}
//此题似乎要开long long 
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;++i){
        scanf("%lld",&a[i].val),a[i].idx=i;
        if(!top)st[++top]=a[i];
        else {
            while(st[top].val>a[i].val){ans=Max(ans,st[top].val*(i-st[top-1].idx-1));top--;}//计算弹出去元素的美丽值
            //i-st[top-1].idx-1是这个弹出元素管理的区间 
            //必须计算弹出元素的美丽值,因为有可能成为最大的美丽值 
            st[++top]=a[i];//入栈 
        }
    }
    for(int i=1;i<=top;++i){
        ans=Max(ans,(N-st[i-1].idx)*st[i].val);//遍历栈  
    }
    printf("%lld",ans);
    return 0;
}