dtcms 行测 jetbrains Git 程序设计 摩尔投票法 数据算法 java class OpenCV4 Java开发手册 ssh命令 canal安装 multithreading dll get ios4 Material UI bootstrap日历插件 spark文档 excel动态图表制作 pip环境变量 bootstrap文本框 matlab中如何定义函数 matlab中不等于怎么表示 matlab插值函数 oracle数据库创建表空间 mysql数据库 mysql 连接 java9 java编程学习 java操作mysql javarandom javalist 怎么看java版本 java中collection java的安装 远程登录linux javascript基础 魔兽世界字体包 sql综合利用工具
当前位置: 首页 > 学习教程  > 编程语言

排队【单调栈】

2020/8/11 19:43:46 文章标签:

Time Limit:10000MS Memory Limit:65536K
Total Submit:5 Accepted:2
Case Time Limit:1000MS


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


Sample Input
6
5
10
3
7
4
12
2

Sample Output
5


解题思路
这道题可以用单调栈。
单调栈有以下两个性质:
1、若是单调递增栈,则从栈顶到栈底的元素是严格递增的。若是单调递减栈,则从栈顶到栈底的元素是严格递减的。
2、越靠近栈顶的元素越后进栈。
单调栈与单调队列不同的地方在于栈只能在栈顶操作,因此一般在应用单调栈的地方不限定栈的大小,否则可能会造成元素无法进栈。

元素进栈过程:对于单调递增栈,若当前进栈元素为e,从栈顶开始遍历元素,把小于e或者等于e的元素弹出栈,直接遇到一个大于e的元素或者栈为空为止,然后再把e压入栈中。对于单调递减栈,则每次弹出的是大于e或者等于e的元素。

此题的单调栈是递减的。


代码

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long n,a[80010],h[80010],dep,ans,t;//a表示读入数列;h表示单调栈,h记录的数是插入单调栈的数在a中的下标
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	a[n+1]=0x3f3f3f3f;
	h[1]=n+1;//我们假设a[n+1]=inf,因为右边界不会超过n,注意记录的是下标
	t=1;
	for(int i=n;i>=1;i--)
	{
		while(a[h[t]]<a[i]&&t)
			t--;//如果当前数比后面的数要大,后面的数是没有贡献的,直接弹掉
		ans+=h[t]-i-1;//此时栈顶的数是右边第一个大于等于a[i]的数,那么中间的数都比a[i]小,统计进答案
		h[++t]=i;//把当前数插入栈中
	}
	printf("%lld",ans);
}

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

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?