4.24枚举
枚举 · 例8扩展-校门外的树：hard
https://ac.nowcoder.com/acm/contest/20960/1010
#include <bits/stdc++.h>
using namespace std;
long long len, n;
struct q {
long long x;
long long y;
} a[100010];
bool cmp(q a, q b) {
return a.x < b.x;
}
int main() {
cin >> len >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].x >> a[i].y;
if (a[i].x > a[i].y) swap(a[i].x, a[i].y);
}
sort(a + 1, a + n + 1, cmp);
long long l = a[1].x, r = a[1].y;
long long cnt = len + 1; // 总树数初始为 len + 1
for (int i = 2; i <= n; i++) {
if (a[i].x <=r) { // 有重叠部分
r = max(r, a[i].y); // 合并区间
} else {
cnt -= (r - l + 1); // 减去当前区间的树的数量
l = a[i].x;
r = a[i].y;
}
}
cnt -= (r - l + 1); // 减去最后一个区间的树的数量
cout << cnt;
return 0;
}
思路：用一个结构体存每个区间的左右端点，然后对区间左界排序，目的是实现重合区间合并。
感受：没听课程时，自己想的也是把区间给合并以下，但是实现的时候没有想到用两个指针l、r维护左右界，而是想的把合并后的区间保存下来，最后遍历减去。
细节：最后一次更新lr跳出for循环了，但是长度没有更新，所以还需更新长度，合并区间时可能是端点重合，所以应该是a[i].x<=r要加等号的
点点互动一面32人在聊
