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

作者: wjyyy 分类: DP,单调队列/单调栈,解题报告 发布时间: 2018-05-19 15:58

点击量:66

 单调栈优化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;
}

 

 

说点什么

avatar
  Subscribe  
提醒
/* */