题解 P1823 【音乐会的等待】

· · 题解

貌似没有STL题解、、、来一发

维护一个单调栈存储每个人的身高，使栈上方的数<=下方的

当一个身高比栈顶高的人要进栈时，先将栈中所有身高比他矮(不包括相同的)的人弹掉，弹掉几个答案就加几个

原理：

比如要弹掉栈顶的第二个人，因为栈顶的第一个人一定比第二个人和当前要进栈的人矮，所以第二个人和要进栈的人可以互相看见，接下去循环(每次弹掉的人都比之前夹着的人要高，所以可以弹)，懂了吗？

当要进栈的人和栈中的人身高相等时，因为相等也看得见，也要加进答案，有几个加几个，但是不弹出

经过处理身高矮的和身高相等的后，判断除了相等的，栈中还有(比它高的)东西吗，如果有，答案就要多+1(s)，因为要进栈的数和当前比它大一级的数(将比它矮和相等的弹出之后的栈顶)也是可以互相看见的，(但是比它大两级的因为中间有夹一个大一级的所以就看不见，所以只能加上1)

这样子就可以了，其实也蛮水的，就是思维性比较强一点

#include<stack>
#include<iostream>
using namespace std;
int x,n,ans;
stack<int>s;
int main()
{
    cin>>n;
    while (n--)
    {
        cin>>x;int t=1;  //t是有多少个跟x相等的(包括x它自己)，(我是先将相等也先弹掉，这样好判断还有没存在比x大一级的数(相等的也弹掉之后的栈顶)，之后再把t个相等的弄回栈中，因为t一开始=1，所以执行t次入栈的时候就将x自己也进栈了)
        while (s.size() && x>=s.top()) //弹掉比它大或等于的同时更新答案
        {
            if (s.top()==x)t++;  //有一个相等就+1(s)
            ans++;s.pop();
        }
        if (s.size())ans++;   //如果把矮的和相等的都弹掉之后还有比x大的就+1
        while (t--)s.push(x); //把之前弹掉的相等的和x本身进栈
    }
    cout<<ans;
    return 0;
}