P1823 音乐会的等待

题目描述

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
分析:当输入一个数时。如果栈中有和这个数相等的数或这比他小的数,则这些数都可以和他看见,ans++,并且我们可以先把这些数pop掉,之后的栈顶一定会比现在的数大,也
能和他看见,所以ans++。
那么这样处理会有一个漏洞,比如这组数据
7
11 10 10 8 9 10 10
当输入第6个10时,会按照上面所说的,找比他小的或相等的,会找到4个数,ans++四次,这是会发现8其实看不见,??
那么我们在处理完上面的过程后,要把相同的数在都加入栈,而那些比他小的数不需要(因为当前数把他们挡着了),而相同的数则可能会被看见。
 #include<cstdio>
#include<stack>
using namespace std; stack<int>s;
int n,m,t,ans; int main()
{
scanf("%d",&n);
while (n--)
{
t = ;
scanf("%d",&m);
while (s.size() && m>=s.top())
{
if (m==s.top()) t++;
ans++;
s.pop();
}
if (s.size()) ans++;
while (t--) s.push(m);
}
printf("%d",ans);
return ;
}
05-11 13:46