题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(nm)$
开一个n大小的数组,然后依次标记区间即可(我为了让下标从1开始,下面的代码中坐标都加了1)
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int n,m;
bool f[10005];
int ans;
int main() {
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++) {
int l,r;
scanf("%d %d",&l,&r);
l++;
r++;
for(int j=l;j<=r;j++) {
f[j]=1;
}
}
for(int i=1;i<=n+1;i++) {
if(!f[i]) {
ans++;
}
}
printf("%d",ans);
return 0;
}
算法2
(差分) $O(n+m)$
注意到只需要在最后输出结果,我们就可以利用差分思想,用f[l]++,f[r+1]–表示覆盖一个区间[l,r]
最后跑一次前缀和,统计未被覆盖的点
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int n,m;
int f[10005];
int ans;
int main() {
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++) {
int l,r;
scanf("%d %d",&l,&r);
l++;
r++;
f[l]++;
f[r+1]--;
}
for(int i=1;i<=n+1;i++) {
f[i]+=f[i-1];
if(f[i]==0) {
ans++;
}
}
printf("%d",ans);
return 0;
}
蒟蒻第一次写题解,请多多指教qwq