题目描述
N 个人正在排队进入一个音乐会人们等得很无聊, 于是他们开始转来转去, 想在队伍里寻找自己的熟人队列中任意两个人 A 和 B, 如果他们是相邻或他们之间没有人比 A 或 B 高, 那么他们是可以互相看得见的
写一个程序计算出有多少对人可以互相看见
输入输出格式
输入格式:
输入的第一行包含一个整数 N (1 N 500 000), 表示队伍中共有 N 个人
接下来的 N 行中, 每行包含一个整数, 表示人的高度, 以毫微米 (等于 10 的 - 9 次方米) 为单位, 每个人的调度都小于 2^31 毫微米这些高度分别表示队伍中人的身高
输出格式:
输出仅有一行, 包含一个数 S, 表示队伍中共有 S 对人可以互相看见
输入输出样例
输入样例 #1:
- 7
- 2
- 4
- 1
- 2
- 2
- 5
- 1
输出样例 #1:
10
啥也不会, 一上来就写的暴力果然是太弱了, 加油啊
正解:
单调栈, 维护一个单调栈, s[top]<=s[top-1]......
如果当前元素>=s[top], 就把当前元素出栈, 说明这是当前元素可以看见的,
同时更新答案
如果到当前元素 < s[top] && top>=1 时, 就说明找到了他能看到的最远的人的最高距离, 更新答案
然后把当前元素以及重复的入栈
详见代码
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cmath>
- #include<vector>
- #include<map>
- #include<queue>
- #define ll long long
- #define inf 2147483600
- #define DB double
- #define eps 1e-6
- using namespace std;
- const int N=500010;
- int n,h,s[N],ans,top,k;
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;++i)
- {
- scanf("%d",&h);k=1;
- while(top>=1 && h>=s[top])
- {
- if(s[top]==h) k++;
- top--,ans++;
- }
- if(top) ans++;
- while(k--) s[++top]=h;
- }
- printf("%d",ans);
- return 0;
- }
- View Code
人生真的是付出多少就收获多少, 那么, 就然我从现在开始努力耕耘吧
不怕晚, 就怕不努力
来源: http://www.bubuko.com/infodetail-2509346.html