AcWing 422. 校门外的树——大白话解析
原题链接
简单
作者:
z_AC
,
2024-03-13 21:22:08
,
所有人可见
,
阅读 18
/*
这个问题主要是怎么计算中间的这个差值,开头部分就是最小值的区间的左边界
然后中间就是在进行区间合并的时候记录一下 并且要将长度减一 最后直接用L值-最左边界
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
int l,m;
vector<PII> segs;
int main() {
cin>>l>>m;
for(int i = 0;i < m;i++) {
int l,r;
cin>>l>>r;
segs.push_back({l,r});
}
int res = 0;
sort(segs.begin(),segs.end());
res = segs[0].first;
// cout<<res<<endl;
vector<PII> ans;
int st = segs[0].first,ed = segs[0].second;
for(int i = 1;i < m;i++) {
if(ed < segs[i].first - 1) {
// cout<<segs[i].first - ed - 1<<endl;
res += segs[i].first - ed - 1;
ans.push_back({st,ed});
st = segs[i].first,ed = segs[i].second;
}else {
ed = max(ed,segs[i].second);
}
}
// cout<<ed<<endl;
// cout<<l - ed<<endl;
res += l - ed;
cout<<res<<endl;
return 0;
}