▼

APCS 實作題 10503 第3題線段覆蓋長度參考解法

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

此題在高中生程式解題系統的題號為：b966: 第 3 題 線段覆蓋長度。

筆者的解題作法：
方法一(C程式碼)：
此方法有可能會得到70分，無法得到100分，但高中生程式解題系統讓筆者過了！？
用一個布林陣列 p 來記錄那些地方有被畫線，以及紀錄所有線段上的最小值 min 與最大值 max，接著用迴圈從 min 到 max 計算有多少地方被畫線，見下圖。

方法二(C++程式碼)：
使用一個結構陣列 struct Point p 來記錄所有線段，並將此結構陣列由小排到大(見下圖)，
接著在判斷目前的線段是否有所覆蓋下一個線段，而這有三種狀況：
1. 完全覆蓋下一線段，此情況直接繼續下一線段的判斷。
2. 部分覆蓋，將目前線段的結尾更新為下一線段的結尾。
3. 沒有覆蓋下一線段，計算目前連線起來的線段長度，並加總到總長度 cnt 。

C程式碼：
 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 <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define NUM 10000000
bool p[NUM];

int main(void)
{
    int n;
    while(scanf("%d",&n) != EOF )
    {
        // 清除標記
        memset(p,0,sizeof(char));
        int a, b, min = NUM, max = -1;

        for(int i = 0; i < n; i++)
        {
            scanf("%d%d", &a, &b);

            if(min > a) min = a;
            if(max < b) max = b;

            for(int j = a; j < b; j++)
                p[j] = 1;   // 畫線標記
        }

        // 計算長度
        int cnt = 0;
        for(int i = min; i < max; i++)
            if(p[i] == 1) cnt++;

        printf("%d\n", cnt);
    }

    return 0;
}


C++程式碼：
 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
#include <iostream>
#include <algorithm>

using namespace std;

#define NUM 10000
struct Point
{
    int s;
    int e;
};

Point p[NUM];

int cmp(Point p1, Point p2)
{
    if(p1.s == p2.s) return p2.e > p1.e;
    else return p2.s > p1.s;
}

int main(void)
{
    int n;

    while (cin >> n)
    {
        for(int i = 0; i < n; i++)
            cin >> p[i].s >> p[i].e;

        sort(p, p + n, cmp);   // 將所有線段由小排到大

        int cnt = 0, s, e;
        for(int i = 0; i < n; i++)
        {
            s = p[i].s;
            e = p[i].e;

            while(i + 1 < n && p[i+1].s < e) // 是否有覆蓋到下一線段
            {
                if(p[i+1].e < e) i++;   // 覆蓋到下一線段的全部
                else
                {
                    e = p[i+1].e;       // 有部分覆蓋到下一線段，以下一線段的結尾 e 當成目前的結尾。
                    i++;
                }
            }
            cnt += e - s;   // 計算線段長度
        }

        cout << cnt << endl;
    }

    return 0;
}

沒有留言:

張貼留言