AcWing 422. 校门外的树
原题链接
简单
作者:
LeeDV
,
2024-04-07 11:37:08
,
所有人可见
,
阅读 1
如果区间内不包含断点,建地铁的区域剩余区域要加上一个端点处的数(不-1),否则剩余区域都-1
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
struct node
{
int l,r;
bool operator<(const node&s)const
{
if(l==s.l)return r<s.r;
return l<s.l;
}
}nodes[N];
int L,m;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>L>>m;
for(int i=0;i<m;i++)
{
cin>>nodes[i].l>>nodes[i].r;
}
sort(nodes,nodes+m);
int st=0,ed=-1;
int res=0;
for(int i=0;i<m;i++)
{
if(ed<nodes[i].l)
{
if(ed==-1)
{
if(nodes[i].l-st>0)res+=(nodes[i].l-st);
st=nodes[i].l;
ed=nodes[i].r;
}else{
res+=nodes[i].l-ed-1;
st=nodes[i].l;
ed=nodes[i].r;
}
}else
{
ed=ed>nodes[i].r?ed:nodes[i].r;
}
}
if(ed!=-1)
{
if(L-ed>0)res+=L-ed;
}
cout<<res<<endl;
return 0;
}