这题数据量不大,有多种方法处理,这里我列举三种仅供参考
算法1:(暴力模拟)
时间复杂度最高O(m*l)
#include <iostream>
using namespace std;
int a[10010];
int main()
{
int l,m,left,right,res=0;
cin>>l>>m;
for(int i=0;i<m;i++)
{
cin>>left>>right;
for(int j=(left>=0?left:0);j<=(right<=l?right:l);j++)
{
a[j]++;
}
}
for(int i=0;i<=l;i++)
if(!a[i]) res++;
cout<<res<<endl;
return 0;
}
算法2:(差分前缀和思想)
时间复杂度最高O(m+l)
#include <iostream>
using namespace std;
int a[10010];
int main()
{
int l,m,left,right,res=0,sum=0;
cin>>l>>m;
for(int i=0;i<m;i++)
{
cin>>left>>right;
a[left>=0?left:0]++;
a[right<=l?right+1:l+1]--;
}
for(int i=0;i<=l;i++)
{
sum+=a[i];
if(sum==0) res++;
}
cout<<res<<endl;
return 0;
}
算法3:(区间合并)
时间复杂度最高O(mlog m)
#include <iostream>
#include <algorithm>
using namespace std;
struct Edge
{
int x,y;
}edge[110];
bool cmp(Edge a, Edge b)
{
return a.x<b.x;
}
int main()
{
int l,m;
cin>>l>>m;
for(int i=0;i<m;i++)
{
cin>>edge[i].x>>edge[i].y;
edge[i].x=max(edge[i].x,0);
edge[i].y=min(edge[i].y,l);
}
sort(edge,edge+m,cmp);
int left=edge[0].x,right=edge[0].y,cnt=0;
for(int i=1;i<m;i++)
{
if(edge[i].x<=right)//区间合并
right=max(edge[i].y,right);
else
{
cnt+=right-left+1;
right=edge[i].y;
left=edge[i].x;
}
}
cnt+=right-left+1;
cout<<l+1-cnt<<endl;
return 0;
}