枚举 · 例8扩展-校门外的树：hard

登录—专业IT笔试面试备考平台_牛客网

代码区：

#include<algorithm>
#include<iostream>
#include<vector>using namespace std;
struct TREE{int left,right;
};
bool compare(const  TREE&a,const TREE& b ){if(a.left!=b.left){return a.left<b.left;}return a.right<b.right;
}
int main(){long long l,n,move_count=0;cin>>l>>n;vector<struct TREE> tree(n);for(int i=0;i<n;i++){int a,b;cin>>a>>b;struct TREE temp_tree;temp_tree.left=a;temp_tree.right=b;tree[i]=temp_tree;}//按照左端点升序排列，左端点相同，按照右端点升序排列sort(tree.begin(),tree.end(),compare);//如何判断是否存在覆盖区域int current_right=-1;for(int i=0;i<n;i++){//不存在覆盖区域，下一个区域的左端点>本次区域的右端点if(tree[i].left>current_right){move_count+=(tree[i].right-tree[i].left+1);current_right=tree[i].right;}//存在覆盖区域,只需要加上未被覆盖的部分else if(tree[i].right>current_right){move_count+=(tree[i].right-current_right);current_right=tree[i].right;}}cout<<l+1-move_count;return 0;
}

欢迎各位读者提出意见。

（菜菜奋斗小日记）