分析
对于一条路径[a, b],判断其是否被交叉,只需要考虑两方面其一成立即可
第一:对于a点左边的所有路径的最大的b大于当前路径的b
第二:对于a点右边的所有路径的最小的b小于当前路径的b
基于此思路,采用双堆算法,但是需要动态删除指定元素,数据没有重复,所以这里采用set代替heap实现。
代码一
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct road{
int a, b;
bool operator < (const road& r) {
return a < r.a;
}
}road[N];
int main()
{
int n;
scanf("%d", &n);
set<int> l, r;
for(int i = 0; i < n; i++) {
scanf("%d%d", &road[i].a, &road[i].b);
r.insert(road[i].b);
}
sort(road, road + n);
int ans = 0;
for(int i = 0; i < n; i++) {
int b = road[i].b;
if(i == 0) {
int right = *r.begin();
if(b > right) ans++;
r.erase(b);
l.insert(-b);
} else if(i == n - 1) {
int left = -*l.begin();
if(left > b) ans++;
} else {
int right = *r.begin(), left = -*l.begin();
if(right < b || left > b) ans++;
r.erase(b);
l.insert(-b);
}
}
printf("%d\n", n - ans);
return 0;
}
代码二
前缀最大/后缀最小预处理
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct road{
int a, b;
bool operator < (const road& r) {
return a < r.a;
}
}road[N];
int l[N], r[N];
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d%d", &road[i].a, &road[i].b);
}
sort(road, road + n);
int ans = n;
l[0] = road[0].b, r[n - 1] = road[n - 1].b;
for(int i = 1; i < n; i++) {
l[i] = max(l[i - 1], road[i].b);
}
for(int i = n - 2; i >= 0; i--) {
r[i] = min(r[i + 1], road[i].b);
}
for(int i = 0; i < n; i++) {
int b = road[i].b;
if(i == 0 && r[i] < b || i == n - 1 && l[i] > b) ans--;
else if(i > 0 && i < n && (l[i] > b || r[i] < b)) ans--;
}
printf("%d\n", ans);
return 0;
}
代码1应该就是用两个堆来维护前缀最大值 和 后缀最小值吧, 用set来模拟堆,即可以即可删除堆中元素,学到了!!!
没错