【SSL2882】排队
Descriptionn个人排成一条直线(一排),给出队伍中每个人的身高,每个人只能看到站在他右边且个头比他小没有被其他人挡住(跟他身高相同也会挡出他)的人。请求出所有人可以看到的人数之和。1<=N<=80,000InputOutputSample Input610374122Sample Output5思路:我们可以用单调栈来做这道题每次找到右边第一个比它大的人,然后计算之间的距离代
·
Description
n个人排成一条直线(一排),给出队伍中每个人的身高,每个人只能看到站在他右边且个头比他小没有被其他人挡住(跟他身高相同也会挡出他)的人。请求出所有人可以看到的人数之和。
1<=N<=80,000
Input
Output
Sample Input
6
10
3
7
4
12
2
Sample Output
5
思路:
我们可以用单调栈来做这道题
每次找到右边第一个比它大的人,然后计算之间的距离
代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
stack<long long>q;
long long n, a[100100];
int main()
{
scanf("%lld", &n);
for(int i=1; i<=n; i++)scanf("%lld", &a[i]);
a[n+1]=0x3f3f3f3f;//给他建一堵墙,让所有人都撞得着
q.push(n+1);
long long ans=0;//十年OI一场空,不开LL见祖宗
for(long long i=n; i>=1; i--)
{
while(!q.empty()&&a[i]>a[q.top()])q.pop();
ans+=q.top()-i-1;//计算其间距离
q.push(i);
}
printf("%lld", ans);
return 0;
}
更多推荐
所有评论(0)