题目描述
学校大门外长度为的马路上有一排树，每两棵相邻的树之间的间隔都是1米。可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在的位置，数轴上的每个整数点(即0，1，2，……，)都有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任意区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树(包括区域端点处的两棵树)移走。请计算将这些树都移走后，马路上还有多少棵树。
输入
样例输入
500 3
150 300
100 200
470 471
样例输出
298
做法1 —— 模拟
#include <bits/stdc++.h> using namespace std; int main() { int L, M; cin >> L >> M; vector<int> trees(L + 1, 1); while (M--) { int l, r; cin >> l >> r; fill(trees.begin() + l, trees.begin() + r + 1, 0); } cout << accumulate(trees.begin(), trees.end(), 0); return 0;
做法2 —— 排序
#include <bits/stdc++.h> using namespace std; struct Segment { /* 线段的左端点和右端点 */ int left, right; Segment(int left, int right) : left(left), right(right) {} /* 对优先队列的“小于号”进行重载 */ bool operator<(const Segment &other) const { /* C++中的优先队列默认实现为最大堆 此处我们需要使用“大于号”以实现最小堆 */ return left > other.left || (left == other.left && right > other.right); } bool operator==(const Segment &other) const { return left == other.left && right == other.right; } /* 对线段进行合并 如成功合并返回true 否则返回false */ bool merge(const Segment &other) { /* 不相交 - 线段1的右端点 在 线段2的左端点 的左侧 */ if (right < other.left) return false; /* 相交 - 合并后的线段存放在线段1中 左端点不变 右端点取两者中较大值 */ right = max(right, other.right); return true; } }; int main() { int L, M; cin >> L >> M; priority_queue<Segment> pq; for (int i = 0, left, right; i < M; ++i) { cin >> left >> right; pq.emplace(Segment(left, right)); } int cnt = 0; while (pq.size() >= 2) { Segment s1 = pq.top(); pq.pop(); Segment s2 = pq.top(); pq.pop(); if (s1.merge(s2)) { pq.push(s1); } else { /* 两条线段不相交 因此线段1不会与任何线段相交 统计线段1中被砍伐的树木数量 */ cnt += s1.right - s1.left + 1; /* 线段2并未参与合并过程 将其退回堆中等待下次操作 */ pq.push(s2); } } /* 堆中最后还剩下一条未处理的线段 */ if (!pq.empty()) cnt += pq.top().right - pq.top().left + 1; cout << L + 1 - cnt << endl; return 0; }
