算法1
(暴力枚举) $O(ML)$
直接模拟暴力枚举,时间复杂度如上。
#include<iostream>
const int maxn = 1e4 + 1;
using namespace std;
bool a[maxn];
int n,m;
int main() {
cin >> n >> m;
while(m--) {
int l,r;
cin >> l >> r;
for(int i = l; i <= r; i++) a[i] = true;
}
int ans = 0;
for(int i = 0; i <= n; i++) ans += (a[i] == 0);
cout << ans << endl;
}
这个时间复杂度是比较显然的,所以说不多讲
算法2
(差分) $O(n)$
通过差分的思想来操作 l 到 r,从而达到 $O(n)$ 的时间复杂度完成该题。
C++ 代码
#include<iostream>
using namespace std;
const int maxn = 1e4 + 1;
int a[maxn],b[maxn];
int n,m;
int main() {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int l ,r;
cin >> l >> r;
b[l] ++;
b[r + 1]--;
}
int ans = 0;
for(int i = 0; i <= n; i++) {
a[i] = a[i - 1] + b[i];
ans += (a[i] == 0);
}
cout << ans << endl;
return 0;
}
较之普通的模拟更加优秀、
希望大家可以学习差分这种思想,在区间问题中是十分高效而且好想的一种算法。