AcWing 422. 校门外的树
原题链接
简单
作者:
初九
,
2021-07-20 19:57:57
,
所有人可见
,
阅读 206
思路
首先通过区间合并合并所有要建地铁的区间,然后减去这些区间就可以得到省下来的距离,
需要注意的是,本题中要求省下来的树的数量,因此在计算端点的时候,可能需要加一
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
PII a[105];
vector<PII> t;
int main(){
int l,m;
cin>>l>>m;
for(int i=0;i<m;i++) cin>>a[i].first>>a[i].second;
sort(a,a+m);
int llim=a[0].first,rlim=a[0].second;
for(int i=1;i<m;i++){
if(a[i].first<=rlim) rlim=max(rlim,a[i].second);
else{
t.push_back(make_pair(llim,rlim));
llim=a[i].first;rlim=a[i].second;
}
}
t.push_back(make_pair(llim,rlim));
for(int i=0;i<t.size();i++){
l=l-(t[i].second-t[i].first+1);
}
cout<<l+1<<endl;
return 0;
}