2022.2.3 训练日记7 AcWing 1978. 奶牛过马路

题目链接：奶牛过马路

题目分析：

0.排序 + 前缀最值
1.题解如下：

题解

code:

#include <iostream>
#include <cstring>
#include <algorithm>#define x first
#define y secondusing namespace std;typedef pair<int, int> PII;const int N = 100010, INF = 1e8;int n;
PII q[N];
int smax[N], smin[N];//前缀最值int main()
{
    cin >> n;for(int i = 1; i <= n; i ++) scanf("%d%d", &q[i].x, &q[i].y);//存储每条线的信息sort(q + 1, q + 1 + n);smax[0] = -INF, smin[n + 1] = INF;//预处理前缀最值for(int i = 1; i <= n; i ++) smax[i] = max(smax[i - 1], q[i].y);for(int i = n; i; i --) smin[i] = min(smin[i + 1], q[i].y);int res = 0;for(int i = 1; i <= n; i ++)if(smax[i - 1] < q[i].y && smin[i + 1] > q[i].y) res ++;printf("%d\n", res);return 0;
}

总结：

1.前缀最值 + 后缀最值。可以预处理也可以边计算边处理。