CANopen scipy 后端面试 pdf mockito Seajs History.js Web Uploader vue入门 ddos压力测试 java并发编程视频 js获取焦点事件 webform开发教程 matlab不等于怎么表示 bootstrap居中对齐 mysql建表主键自增长 flutter项目案例 python数据类型 pythonapi python基础语法 java获取当前年份 java中的基本数据类型 linux教程 内存整理工具 战地2单机地图 linux解压tar workflow中文 js删除节点 php取整函数 音乐剪辑器下载 通讯录管理系统 批处理if mpg格式转换 ansys安装教程 c4d挤压怎么用 驱动精灵绿色版 php验证码 谷歌地球怎么用不了 opencv是什么 ppt虚线怎么画
当前位置: 首页 > 学习教程  > 编程语言

【单调栈】排队

2020/8/11 20:18:22 文章标签:

Description

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

Sample Input
6    
5
10
3
7
4
12
2
Sample Output
5

解题思路

递减单调栈
计算答案,找到当前ii的右边的墙,用下标互减


code

#include<iostream> 
#include<cstdio>
using namespace std;
long long n,top,a[80100],f[80100],ans;
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	    scanf("%lld",&a[i]);
    a[n+1]=0x3f3f3f3f;//建右边的墙
    f[++top]=n+1;
	for(int i=n;i>0;i--){//从右往左找
		while((top)&&(a[f[top]]<a[i]))top--;//如果右边比它矮的,那么就不会对更左边的木板产生墙贡献,出栈
		ans+=f[top]-i-1;//下标互减计算答案
		f[++top]=i;//压入栈
	}
	printf("%lld",ans);
}

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

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?