传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1113
题解：单调栈
代码：
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<algorithm>
5 #define maxn 250005
6 using namespace std;
7 int n;
8 int a[maxn],b[maxn],z[maxn];
9 int main()
10 {
11 scanf(
"%d\n",&
n);
12 int mmax=
0,top=
0,ans=
0;
13 for (
int i=
1; i<=n; i++) scanf(
"%d%d",&a[i],&b[i]),mmax=
max(mmax,b[i]);
14 z[
0]=
0;
15 for (
int i=
1; i<=n; i++
)
16 {
17 while (z[top]>b[i]) top--
;
18 if (z[top]<b[i]) ans++
;
19 z[++top]=
b[i];
20 }
21 printf(
"%d\n",ans);
22 }
View Code
转载请注明原文地址: https://ju.6miu.com/read-1301054.html
