Problem Solving►UVa

UVa 10020 - Minimal coverage

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址

給定 M ，和數個區段，找出使用最少區段覆蓋 [0,M] 的方法。
p.s. 區段可重疊。

Solution

先將各區段依左邊界排序。
每次都先找左邊界最小的，看左邊界是否可以從已覆蓋的區域開始接(一開始當然是從 -INF 到 0 )，如果不行則代表兩段之間會有空隙，即無法完成。
從多個符合條件(不會產生空隙)的區段中找右邊界最遠的，且其右邊界超過已覆蓋區域的右邊界。
重複以上直到覆蓋完 [0,M]。

Code

UVa 10020UVa 10020 - Minimal coverage
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<cstdio>
#include<algorithm>
#define N 100000
using namespace std;
struct Seg
{
    int l, r;
}seg[N];
int main()
{
    int Case;
    scanf("%d", &Case);
    while (Case--)
    {
        int tar, i = 0, l, r;
        scanf("%d", &tar);
        while (scanf("%d%d", &l, &r) && (l || r))
        {
            seg[i].l = l;
            seg[i].r = r;
            i++;
        }

        int count = i;
        sort(seg, seg + count, [](const Seg& a, const Seg& b)->bool
        {
            return a.l < b.l;
        });

        int now = 0, ans = 0, ans_idx[N];
        int max, idx;
        for (i = 0; i < count; ans++)
        {
            if (now >= tar)//已完成
                break;

            if (seg[i].l > now)//剩下區段的左端點已大於目前完成的了，會有空隙
            {
                ans = 0;
                break;
            }
            else 
            {
                //從剩下的段落找出符合 "左端點小於等於目前完成的" ，其中 最遠的右端點
                max = seg[i].r;
                idx = i;
                while (i < count&&seg[i].l <= now)
                {
                    if (max < seg[i].r)
                    {
                        max = seg[i].r;
                        idx = i;
                    }

                    i++;
                }

                if (max <= now)//如果剩下區段的右端點，皆無法覆蓋超過現在完成的，就無法覆蓋全部區域
                    break;

                now = seg[idx].r;
                ans_idx[ans] = idx;
            }
        }

        if (now >= tar)
        {
            printf("%d\n", ans);
            for (i = 0; i < ans; i++)
                printf("%d %d\n", seg[ans_idx[i]].l, seg[ans_idx[i]].r);
        }
        else
            puts("0");

        if (Case)
            putchar('\n');
    }

    return 0;
}