Zookeeper安装 kubeflow 远程桌面登陆 摩尔投票法 caching encryption plugins smtp Zeptojs vue入门 bootstrap模板 angular视频 change事件 jquery获取元素 matlab停止运行命令 base64转16进制 tomcat调优和jvm调优 matlab中如何定义函数 dwf文件怎么转成dwg python转java hbuilder插件 mysql时间戳转日期 python自学教程 python在线教程 python如何调用函数 python函数内定义函数 java数组扩容 java接口实现 java运行环境 java安装教程 超级兔子ie修复专家 只狼鬼佛 电视免费软件 朋友圈访客记录教程 java字符串截取 linux定时任务 还原软件哪个好 苹果手机怎么滚动截屏 什么是内存条 php队列
当前位置: 首页 > 学习教程  > 编程语言

【SSL 2882】[POJ 3250]排队【单调栈模板】

2020/8/11 19:48:03 文章标签:

排队

Time Limit:10000MS Memory Limit:65536K
Case Time Limit:1000MS

Description

n个人排成一条直线(一排),给出队伍中每个人的身高,每个人只能看到站在他右边且个头比他小没有被其他人挡住(跟他身高相同也会挡出他)的人。请求出所有人可以看到的人数之和。
1<=N<=80,000

Sample Input

6    
10
3
7
4
12
2

Sample Output

5

分析:

这道题其实就是单调栈的模板题

CODE:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long n,ans,a[100005],st[100005],top=1;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	a[n+1]=0x7fffffff;  //右边界不会超过n
	st[1]=n+1;
	for(int i=n;i>0;i--)
	{
		while(a[st[top]]<a[i]&&top) top--;  //出栈
		ans+=st[top]-i-1;  //中间数统计
		st[++top]=i;  //入栈
		
	}
	printf("%lld",ans);
	return 0;
}

本文链接: http://www.dtmao.cc/news_show_100196.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?