首页技术正文

Patrik 音乐会的等待单调栈的迷茫回忆

程序员爱欣技术 2022年11月22日

0 收藏 677 点赞 3,388 浏览 1201 个字

STL 一定要学好一定要学好，一定要学好！！！

题目链接：https://www.luogu.org/problemnew/show/P1823

我们需要单向查找；用单调栈；

思路：
维护一个身高单调递减的栈，如果下一个比上一个插入的矮，就直接进栈，如果现在插入的比上一个高，我们就要更新答案的值；

因为现在要插入的人会挡住前面比他矮的人，所以前面比他矮的人就不能再看见以后的人了；

当然还要记录前面和他一样高的人的个数，因为和他一样高的人是可以看见他后面的人的（题目中是大于没有等于）

因为我们维护的是右端点的值，所以前面的矮人就直接弹出；

代码

#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
using namespace std;
const int maxn=;
stack <int> s;//单调栈
int n,x,ans;
int a[maxn];
int main()
{
    scanf("%d",&n);
    for(int i=;i<=n;i++)
    {
        int t=;//记录和他身高一样的人的个数
        scanf("%d",&x);
        while(s.size()&&x>=s.top())//栈中还有人并且有人比他矮或等高
        {
            if(x==s.top()) t++;
            ans++;s.pop();//因为不弹出就不能查看上一个值，所以即使等高也要弹出
        }
        if(s.size()) ans++;//如果前面有人比他高，那么他们两个人也能互相看到
        while(t--) s.push(x);//将所有不该弹出的等高的人加入栈
    }
    printf("%d",ans);    return ;
}

对不起，TLE

显然我们处理等高的人的时候浪费了大把的时间，所以我们可以把前面和他等高的人的贡献直接加到现在要插入人的身上

用结构体就行了

代码

#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
using namespace std;
const int maxn=;struct node
{
    int h;//高度
    long long num;//前面等高人的个数
};
stack <node> s;
int n,x;
long long ans;
int a[maxn];
int main()
{
    scanf("%d",&n);
    for(int i=;i<=n;i++)
    {
        scanf("%d",&x);
            node p=(node){x,};//记录当前和他等高的人是自己
        while(s.size()&&x>=s.top().h)
        {
            if(x==s.top().h) p.num+=s.top().num;
            ans+=s.top().num;s.pop();
        }
        if(s.size()) ans++;
        s.push(p);    }
    printf("%lld",ans);    return ;
}