PTA 7-1 单调栈

题目

N人们排队等着参加音乐会。人们等得很无聊，于是他们转身去排队寻找熟悉的人。
如果两个人A和B并排站在一起，或者如果他们中间没有人比A或B高，那么他们可以看到对方。

编写一个程序，确定可以看到彼此的成对人数。

输入格式:

第一行输入包含一个整数N（1≤N≤500000），排队的人数。

以下N行中的每一行都包含一个整数，即一个人的身高（以纳米为单位）。

每个人的身高都将小于231纳米。高度是按照人们排队的顺序给出的。

输出格式:

输出可以看到对方的成对人数

• 输入样例:

7
2
4
1
2
2
5
1
1
2
3
4
5
6
7
8

• 输出样例:

10
1

代码

#include
using namespace std;
int st[500010],n,top=1,m;
typedef long long LL;
LL ans;
int main()
{
    cin>>n;
    int a;
    cin>>st[1];
    for(int i=2;i<=n;i++)
    {
        cin>>a;
        if(st[top]>a)
        {
            top++,ans++,st[top]=a;
        }
        else
        {
            int l=1,r=top;
            while(l<r)
            {
                m=(l+r)>>1;
                if(r==l+1)m=r;
                if(a>=st[m])r=m-1;
                else l=m;
            }
            ans+=top-l+1;
            while(top>0&&st[top]<a)top--;
            st[++top]=a;
        }
    }
    cout<<ans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

分析

这道题考察单调栈。

首先分析题目要求，求互相看见人的对数，避免重复，我们选择一种方向进行解答，本解使用从前往后。

继续分析，我们任取一人，这个人所能看见最远的人就是前一个比他高的人，并且这个人高于前面的人，那么他后面的人肯定是无法看到前面的人的。

我们再思考用什么数据结构能维持这个性质，单调栈。

之后我们在往栈插入元素时考虑两点：

第一点往前找到第一个比他大的数

第二点是删除所有比他小的数（再也无法与后续数据产生关联，使用二分实现）

最后即可得出结果