AcWing 422. 校门外的树
原题链接
简单
作者:
Bear_King
,
2021-01-20 17:40:19
,
所有人可见
,
阅读 267
直接桶插法$O(L*n)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int L, n;
bool st[N];
int main()
{
cin >> L >> n;
for (int i = 0; i <= L; i ++ ) st[i] = true;
while (n -- )
{
int a, b;
cin >> a >> b;
for (int i = a; i <= b; i ++ ) st[i] = false;
}
int res = 0;
for (int i = 0; i <= L; i ++ ) res += st[i];
cout << res << endl;
return 0;
}
贪心法:区间合并$O(nlogn)$
注意细节:不要忘记+1
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int m, n;
struct Segment
{
int l, r;
bool operator< (const Segment& t) const//重载小于号实现结构体数组排序规则
{
return l < t.l;//谁左端点小谁排前
}
}seg[N];
int main()
{
cin >> m >> n;
for (int i = 0; i < n; i ++ ) cin >> seg[i].l >> seg[i].r;
sort(seg, seg + n);
int sum = 0;//只要L(i) > R就再sum中记录上一个区间
int L = seg[0].l, R = seg[0].r;
for (int i = 1; i < n; i ++ )
if (seg[i].l <= R) R = max(R, seg[i].r);//如果L(i)在上一个区间里则直接取两个区间最大右端点
else
{
sum += R - L + 1;
L = seg[i].l, R = seg[i].r;
}
sum += R - L + 1;
cout << m + 1 - sum << endl;
return 0;
}