AcWing 422. 校门外的树
原题链接
简单
作者:
不幸到吃土
,
2024-04-18 00:54:56
,
所有人可见
,
阅读 2
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
int len,m;
vector<PII> segs;
int merge(vector<PII> segs){
int res = len + 1;
int st = -1 , ed = -1;
for(auto seg :segs){
if(ed < seg.x){
if(st != -1){
res -= ed - st + 1;
}
st = seg.x , ed = seg.y;
}else{
ed = max(ed,seg.y);
}
}
if(st != -1){
res -= ed - st + 1;
}
return res;
}
int main(){
scanf("%d%d",&len,&m);
for(int i=0;i<m;i++){
int l=0 , r=0;
scanf("%d%d",&l,&r);
segs.push_back({l,r});
}
sort(segs.begin(),segs.end());
int ans = merge(segs);
printf("%d",ans);
return 0;
}
0位置有棵树,想了半天怎么答案差一…