校门外的树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;
}