思路
题意很简单,关键是区间可能重叠,暴力做法就是遍历一遍,但是复杂度就太高了,并且有一种投机想法...
#include<iostream> #include<vector> using namespace std; int main(){ int L, M; while (cin >> L >> M){ vector<int> tree(L + 1, 1); int start, end, cnt = 0; for (int i = 0; i < M; i++){ cin >> start >> end; for (int i = start; i <= end; i++) tree[i] = 0; } for (int i : tree) if (i) cnt++; cout << cnt << endl; } return 0; }
也可以把区间存入数组中,并按照起始位置进行排序,然后有新的区间输入,就进行比较是否有重叠,以及有重叠是否是包含关系。
#include <iostream> #include <vector> #include <algorithm> using namespace std; struct Node{ int start; int end; Node(int start, int end) : start(start), end(end) {} bool operator < (const Node &b) const { return start < b.start; } }; int main(){ int l, m; while (cin >> l >> m){ vector<Node> trees; int start, end; for (int i = 0; i < m; i ++){ cin >> start >> end; trees.emplace_back(start, end); } sort(trees.begin(), trees.end()); int cnt = l + 1; int last = 0; for (Node node : trees) // 区间没有重叠 if (node.start >= last){ cnt -= node.end - node.start + (node.start != last); last = node.end; } // 区间存在重叠 else{ // 不是包含关系 if (node.end > last){ cnt -= node.end - last; last = node.end; } } cout << cnt << endl; } }