N个人正在排队进入一个音乐会。人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。队列中任意两个人A和B，如果他们是相邻或他们之间没有人比A或B高，那么他们是可以互相看得见的。
写一个程序计算出有多少对人可以互相看见。
输入格式：
输入的第一行包含一个整数N (1 ≤ N ≤ 500 000), 表示队伍中共有N个人。
接下来的N行中，每行包含一个整数，表示人的高度，以毫微米(等于10的-9次方米)为单位，每个人的调度都小于2^31毫微米。这些高度分别表示队伍中人的身高。
输出格式：
输出仅有一行，包含一个数S，表示队伍中共有S对人可以互相看见。
7 2 4 1 2 2 5 1
10
维护递减栈即可
注意=的考虑
一开始的模拟是wa了三个点 有bug 见代码
还有三个超级数据点
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3 const int N=1000000; int sta[N]; int main() { int ans=0; CLR(sta,-1); int n; RI(n); int pos=0; while(n--) { int x; RI(x); if(pos==0) { sta[++pos]=x;continue; } int cnt=0; if(sta[pos]>x) sta[++pos]=x,ans++; else { int t=1; while(pos>=1&&sta[pos]<=x) { if(x==sta[pos])t++; ans++;pos--; } if(pos>0)ans++; /* pos++; while(sta[pos]==x)//因为后面可能存在历史遗留数据 pos++; sta[pos]=x; */ while(t--) sta[++pos]=x; } } cout<<ans; return 0; }
将一样的值整合到一起即可
可以用piar的写法
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3 const int N=1000000; int sta[N]; struct node { int cnt,v; }; int main() { stack<node>sta; ll ans=0; int n; RI(n); int pos=0; while(n--) { int x; RI(x); int t=1; while(sta.size()&&sta.top().v<=x) { if(sta.top().v==x)t+=sta.top().cnt; ans+=sta.top().cnt; sta.pop(); } if(sta.size())ans++; node u; u.v=x; u.cnt=t; sta.push(u); } cout<<ans; return 0; }
P1823 [COI2007] Patrik 音乐会的等待 单调栈
原文：https://www.cnblogs.com/bxd123/p/10828972.html
