校门外的树WriteUp

本文最后更新于:2021年5月21日晚上6点49分

原题链接:

ACwing每日一题2021.2.4——校门外的树


AC源代码:

暴力做法:

时间复杂度O(M*N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>

using namespace std;

int main()
{
int l , m, res = 0;
cin >> l >> m;
bool a[l + 1] ;
for ( int i = 0 ; i < l + 1 ; i ++) a[i] = true;
while ( m --)
{
int x, y;
cin >> x >> y;
for ( int i = x ; i <= y ; i ++) a[i] = false;
}
for ( int i = 0 ; i < l + 1 ; i ++)
if ( a[i]) res ++;
cout << res << endl;
return 0;
}
区间合并做法(利用pair)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <algorithm>

using namespace std;
typedef pair<int , int > PII;

PII a[101];


int main()
{
int l , m;
cin >> l >> m;
for ( int i = 0 ; i < m; i ++) cin >> a[i].first >> a[i].second;
sort(a, a + m);
int st = a[0].first , ed = a[0].second;

for ( int i = 0 ; i < m; i ++)
{
if ( a[i].first <= ed ) ed = max(ed, a[i].second);
else
{
l = l - ( ed - st + 1);
st = a[i].first;
ed = a[i].second;
}
}

l -= ed - st + 1;
cout << l + 1 << endl; //l米长度的公路上一共有l + 1棵树。

return 0;
}
区间合并做法(结构体)

以下代码摘自YXC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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;
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);
else
{
sum += R - L + 1;
L = seg[i].l, R = seg[i].r;
}
sum += R - L + 1;
cout << m + 1 - sum << endl;

return 0;
}