洛谷 P1823 音乐会的等待 题解【DP】【单调栈】

点击量：1088

 单调栈优化DP

目录

题目描述

N个人正在排队进入一个音乐会。人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。队列中任意两个人A和B，如果他们是相邻或他们之间没有人比A或B高，那么他们是可以互相看得见的。

 

写一个程序计算出有多少对人可以互相看见。

输入输出格式

输入格式：

输入的第一行包含一个整数N (1 ≤ N ≤ 500 000), 表示队伍中共有N个人。

 

接下来的N行中，每行包含一个整数，表示人的高度，以毫微米(等于10的-9次方米)为单位，每个人的调度都小于2^31毫微米。这些高度分别表示队伍中人的身高。

 

输出格式：

输出仅有一行，包含一个数S，表示队伍中共有S对人可以互相看见。

 

输入输出样例

输入样例#1：

7

2 4 1 2 2 5 1

输出样例#1：

10

说明

数据制作: @w

  这个题要求输出能互相看见的人的对数，普通DP的时间复杂度约为$ O(N^2)$ ，因此对于500000的数据来说，需要用单调栈维护。

  因为两人（设为A,B）之间不能有人高于二者任意一人的高度，因此一旦A后面有一个人C的身高大于A，则可判定A不能被C后面任意一个人看见。

  如果这个题没有重复身高的话，这个题已经做完了当然这是不可能的。这个题会有重复身高，比如1 2 2 2 3中，不是每个2都能看到1，但是3可以看到每个2。对于这种情况，我们要特殊处理。

  为保证栈内元素都是后来有可能被看到的（即没有被遮挡的），栈的单调性是非严格单调递减，相同元素同时存在。

1. 相邻的两个人一定能互相看见，所以如果进栈元素x小于等于栈顶元素，sum++。将元素进栈。
2. 如果x大于栈顶元素，则栈内小于x的元素都可以被x看见，等于x的元素也可以被看见，但是数据要被保留，不出栈。每出栈一个数，将sum++。注意，当满足“小于x”的元素全部出栈后，栈顶如果有元素，那么它也可以被x看见，sum还是要++。回到1。
3. 对于2中提到的“栈顶元素”，如果与x相等，就可以看见栈内所有与x相等的数（一串数）。并且这串数前面的一个元素也可以被x看见（例如3 2 2 2中，新进入一个2，那么它可以看见这一串2以及它们前面的3）。当栈内全部是同一数字时，没有这串数前面的一个元素了，就不用sum++，代码中注释的地方就是这里的体现。
4. 注意，无论何时，如果栈是空的，sum是不用+1的。

   因为$ 500000\times 500000=250000000000>2^{31}-1$，所以需要开longlong

Code：

#include<cstdio>
int s[500050];
int t=0;
void pop(){s[t--]=0;}
void push(int x){s[++t]=x;}
long long int sum=0;
void check(int x)
{
    if(t==0)
        push(x);
    else
        if(x>s[t])
        {
            while(t&&x>s[t])
            {
                sum++;
                pop();
            }
            int p=t;
            while(p>1&&s[p]==x)//判断是否栈内全部是同一数字
            {
                sum++;
                p--;
            }
            if(t>0)
                sum++;
            push(x);
        }
        else
        {
            int p=t;
            while(p>1&&s[p]==x)//判断是否栈内全部是同一数字
            {
                sum++;
                p--;
            }
            sum++;
            push(x);
        }
}
int main()
{
    int n,a;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        check(a);
        /*for(int j=1;j<=t;j++)
            printf("%d ",s[j]);
        printf("    %d\n",sum);用于debug栈内数字*/
    }
    printf("%lld\n",sum);
    return 0;
}