C++ 代码 –》 一般思路 暴力算法
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int M,L;
int main()
{
cin >> M >> L;
vector<int> A(M+1,1); //注意点长度为L, 但树有 L + 1棵, 这里适用vector,若其下标对应的值为1,表示有树
for(int i = 0; i < L; ++i)
{
int a,b;
cin >> a >> b;
for (int i = beg; i <= end; ++i) A[i] = 0; // 将这个区间的值修改为0,表示移除树
}
int cnt = 0; //用于遍历vector,保存容器内1的个数
for_each(A.begin(),A.end(), [&cnt](int a) //for_each遍历,这里适用lambda表达式判断条件,当然这里可以直接适用count_if更简便
{
if(a) ++cnt;
});
cout << cnt<< endl;
return 0;
}
使用count_if
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int M,L;
auto main() -> int
{
cin >> M >> L;
vector<int> A(M+1,1);
for(int i = 0; i < L; ++i)
{
int a,b;
cin >> a >> b;
for (int i = a; i <= b; ++i) A[i] = 0;
}
cout << count_if(A.begin(), A.end(),
[](int a) -> bool
{
return a;
});
return 0;
}
Y总的区间合并写法 时间复杂度低
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int M,L;
vector<pair<int,int>> A;
auto main() -> int
{
cin >> L >> M;
for(int i = 0; i < M; ++i)
{
int a, b;
cin >> a >> b, A.push_back({a,b});
}
sort(A.begin(),A.end());
int beg = 0, end = -1; // end = -1,这个写法为啥初始为-1,可以参考下面for取第一段区间时的过程,这样写就不用特判和额外处理
int cnt = 0;
for(int i = 0; i < M ; ++i)
{
if(A[i].first > end) cnt += end - beg + 1, beg = A[i].first, end = A[i].second;
else end = max(A[i].second, end);
}
cnt += end - beg + 1; // 最后更新完 beg, end 后还要手动计算完最后更新完的区间
cout << L + 1 - cnt << endl;
return 0;
}
注意的地方
- 注意这里的起始坐标是 0 ~ L
- 注意点长度为L, 但树有 L + 1棵,