Dark`Kris

Private blog

I'm spark , hope you fire


Luogu 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


解题思路

单调栈

以序列8,8,6,4,2,3,7为例 考虑前五个人,如图右上 考虑加入身高为3的人,如图右下 于是,身高为2的人再也无法被后面的人看见

音乐会的等待

栈的单调性:单调递减 每次将栈中元素个数加入答案,并将A入栈。A入栈是必须的,所以,为了维护栈的单调性,必须将某些栈中的元素弹出,即这些元素所代表的人是会被A挡住,无法与A后面的任何人相互看见的。 时间复杂度:O(N) — 每个元素最多入栈一次出栈一次 细节:不要忘记使用64位整数!

代码如下:

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=500005;
int n,l,ans;
long long q[maxn],bef[maxn];
int main()
{
	cin>>n;
	q[0]=-1;
	long long a;
	for(int i=1;i<=n;i++)
	{
		cin>>a;
		while(l>0&&a>q[l])
		{
			l--;
			ans++;
		};
		if(l!=0)
		{
			if(a!=q[l])ans++;else
			{
				ans+=bef[l];
				if(bef[l]<l)ans++;
			};
		};
		l++;q[l]=a;
		if(q[l-1]==a)bef[l]=bef[l-1]+1;else bef[l]=1;	
	};
	cout<<ans;
	return 0;
}

感谢惠读

Tips

Cancel

Thanks a lot,I will be better!

scan possible
scan possible
Scan and give tips as you wish

OpenAlipayScan it and give tips as you wish

Wait a minute,Loading