音乐会的等待(诺诺的队列)
来源：http://218.5.5.242:9018/JudgeOnline/problem.php?id=1308
题目描述
N个人正在排队进入一个音乐会。人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。队列中任意两个人A和B，如果他们是相邻或他们之间没有人比A或B高，那么他们是可以互相看得见的。
写一个程序计算出有多少对人可以互相看见。
输入
输入的第一行包含一个整数N (1 ≤ N ≤ 500 000), 表示队伍中共有N个人。
接下来的N行中，每行包含一个整数，表示人的高度，以毫微米(等于10的-9次方米)为单位，每个人的调度都小于2^31毫微米。这些高度分别表示队伍中人的身高。
输出
输出仅有一行，包含一个数S，表示队伍中共有S对人可以互相看见。
样例输入
7 2 4 1 2 2 5 1
样例输出
10
代码
|
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 |
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int st[500001],top=1,x; int main() { int n; int l,r,m; cin>>n; long long tot=0; cin>>st[1]; for(int i=2;i<=n;i++){ scanf("%d",&x); if(x<st[top]){ tot++;top++;st[top]=x; } else { l=1; r=top; while (l<r){ m=(l+r)>>1; if (r==l+1) m=r; if (st[m]>x) l=m; else r=m-1; } tot+=top-l+1; while(top>0&&st[top]<x)top--; st[++top]=x; } } cout<<tot<<endl; return 0; } |
Subscribe