剩下的树

思路

题意很简单，关键是区间可能重叠，暴力做法就是遍历一遍，但是复杂度就太高了，并且有一种投机想法...

#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;
    }
}