AcWing 422. 校门外的树
原题链接
简单
作者:
我要出去乱说
,
2021-01-28 00:14:13
,
所有人可见
,
阅读 228
朴素做法
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m;
bool st[N];
int main()
{
cin >> n >> m;
while (m -- )
{
int l, r;
cin >> l >> r;
for (int i = l; i <= r; i ++ ) st[i] = true;
}
int cnt = 0;
for (int i = 0; i <= n; i ++ )
if (st[i])
cnt ++ ;
cout << n - cnt + 1 << endl;
return 0;
}
区间合并法
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m; //n是树木,m是道路段数
struct Seg
{
int l, r;
bool operator< (const Seg& t) const
{
return l < t.l;
}
}seg[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i ++ ) cin >> seg[i].l >> seg[i].r;
sort(seg, seg + m);
int res = 0;
int L = seg[0].l, R = seg[0].r;
for (int i = 1; i < m; i ++ )
if (seg[i].l <= R) R = max(R, seg[i].r);
else
{
res += R - L + 1;
L = seg[i].l, R = seg[i].r;
}
res += R - L + 1;
cout << n - res + 1 << endl;
return 0;
}