P1823 音乐会的等待

题目描述

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

说明

数据制作: @w

这道题一开始自己推出来了如果后面有比他大的那么这个数是没用的,

然后乱搞了一下搞了25分。。。

看了一下题解发现一个非常好的思路

就是把相等和大于放到一个循环里判断,

一开始num==1保证有数据读入

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<stack>
 6 using namespace std;
 7 int read(int & n)
 8 {
 9     char c='-';int x=0;
10     while(c<'0'||c>'9')c=getchar();
11     while(c>='0'&&c<='9')
12     {
13         x=x*10+(c-48);
14         c=getchar();
15     }
16     n=x;
17 }
18 const int MAXN=500001;
19 stack<int>s;
20 int main()
21 {
22     int n,h,ans=0,flag=0;
23     read(n);
24     for(int i=1;i<=n;i++)
25     {
26         flag=0;
27         read(h);
28         if(i==1)
29         {
30             s.push(h);
31             continue;
32         }
33         if(h>s.top())
34         {
35             ans++;
36             s.pop();
37             while(s.size()>0&&h>s.top())
38             {
39                 ans++;
40                 s.pop();
41                 flag=1;
42             }
43             if(s.size()!=0&&h<s.top())
44             ans++;
45             s.push(h);
46         }
47         else if(h==s.top())
48         {
49             ans=ans+s.size();
50             s.push(h);
51         }
52         else
53         {
54             ans++;
55             s.push(h);
56         }
57     }
58     printf("%d",ans);
59 }
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<stack>
 6 using namespace std;
 7 int read(int & n)
 8 {
 9     char c='-';int x=0;
10     while(c<'0'||c>'9')c=getchar();
11     while(c>='0'&&c<='9')
12     {
13         x=x*10+(c-48);
14         c=getchar();
15     }
16     n=x;
17 }
18 const int MAXN=500001;
19 stack<int>s;
20 int main()
21 {
22     int n,h,ans=0,flag=0;
23     read(n);
24     for(int i=1;i<=n;i++)
25     {
26         int num=1;
27         read(h);
28         while(s.size()!=0&&h>=s.top())
29         {
30         
31             if(h==s.top())
32             num++;
33             ans++;
34             s.pop();
35         }    
36         if(s.size()!=0)
37         ans++;
38         while(num--)
39         s.push(h);
40     }
41     printf("%d",ans);
42 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

2973 枪毙

2973 枪毙 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 青铜 Bronze 题目描述 Description   炼哥的朋...

29750
来自专栏小詹同学

【记录帖】从零打卡刷Leetcode——No.007

小詹此记录贴的读者越来越少了,也许是小詹总结的不够好欢迎留言区提出宝贵的意见!也欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一...

14130
来自专栏WeaponZhi

轻松初探 Python 篇(五)—dict 和 set 知识汇总

这是「AI 学习之路」的第 5 篇,「Python 学习」的第 5 篇 dict dict 是 Python 内置的字典类型,熟悉 Java 的同学可以把它类比...

31890
来自专栏编程

Python学习笔记1——斐波那契数列

这是一个高中同学问我的问题,本来是用C来写的,正好正在学Python,就用Python重写了一遍当作练习。 下面是题目要求: ? ? 一道很简单的题目,但有些细...

296100
来自专栏苦逼的码农

从零打卡leetcode之day 1--两数之和

不过心里才两个循环时间复杂度可是n的平方,心想肯定得超时,不过还是大胆提交一下提交,呵呵,居然通过了。。。。

13410
来自专栏带你撸出一手好代码

JavaScript消除游戏实现思路讲解

之前讲解过一款JavaScript贪食蛇游戏详细的设计与实现,但是以那种方式进行描述 , 整篇文章会显得复杂冗长,除非深入细致的阅读和思考,否则文中内容并不容易...

40150
来自专栏ACM算法日常

2018南京大学计算机夏令营机试题

lipper同学问了我一个算法题,由于时间原因没来得及写,lipper同学就自己动手写了出来,并且顺手写了此篇博文,文笔潇洒,与君共勉。

74110
来自专栏数据结构与算法

P3227 [HNOI2013]切糕

题目描述 经过千辛万苦小 A 得到了一块切糕,切糕的形状是长方体,小 A 打算拦腰将切糕切成两半分给小 B。出于美观考虑,小 A 希望切面能尽量光滑且和谐。于是...

354100
来自专栏java达人

HashMap庖丁解牛

感谢erixhao的作品,长文需细品: Code Walkthrough是我们新的一个系列,主要以阅读,分析源代码为主要目的,特此介绍一下。我们先以最经典的JD...

22490
来自专栏Java成神之路

计算字符串相似度算法——Levenshtein

Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。

1K10

扫码关注云+社区

领取腾讯云代金券