跳转链接
https://www.acwing.com/problem/content/1980/
题目描述
每天，农夫约翰的 N 头奶牛都会穿过农场中间的马路。 考虑约翰的农场在二维平面的地图，马路沿水平方向延伸，马路的一侧由直线 y=0 描述，另一侧由直线 y=1 描述。 奶牛 i 从马路一侧的位置 (ai,0) 沿直线过马路到达另一侧的位置 (bi,1)。 所有 ai 互不相同，所有 bi 互不相同。 尽管他的奶牛们行动敏捷，他还是担心行动路径交叉的两头奶牛在过马路时发生碰撞。 约翰认为，如果一头奶牛的行动路径没有跟其他任何奶牛的行动路径相交，则该奶牛是安全的。 请帮助约翰计算安全奶牛的数量。
输入格式 第一行包含整数 N。 接下来 N 行，每行包含两个整数 ai,bi，用来描述一头牛的行动路径。
输出格式 输出安全奶牛的数量。
数据范围 1≤N≤10^5^ , −10^6^≤ai ,bi≤10^6^
输入样例 4 -3 4 7 8 10 16 3 9 输出样例 2
样例解释 第一头牛和第三头牛的行动路线不与其他奶牛的路线相交。 第二头牛和第四头牛的行动路线相交。
题解思路
把所有点对按照 a 的值从小到大排序 对于第 i 个点，只要它之前所有点 b 的最大值小于 bi ， 并且它之后的所有点的 b 的最小值大于 bi 就说明该线路是安全的。 用前缀 smax 数组和后缀 smin 数组优化时间复杂度。
代码
cpp
#include <bits/stdc++.h>
#define x first
#define y second
using 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()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d%d", &q[i].x, &q[i].y);
sort(q + 1, q + 1 + n); //默认优先按照p.x排序
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 > 0; 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", res);
return 0;
}
