題目出自 APCS 網站 > 試題範例 > 2016-03-05_實作題 > 第三題 線段覆蓋長度
連結

解答僅供參考

解答:

#include <stdio.h>
#include <stdlib.h>
#include <cmath>
#include <set>

using namespace std;

#define MAXM 1e8

//線段類別
class Line
{
  public:
    int start; //線段開始位置
    int end;   //線段結束位置

  public:
    Line(int start, int end)
    {
        this->start = start;
        this->end = end;
    }
};

//線段的比較方式
struct LineCompare
{
    bool operator()(const Line *a, const Line *b)
    {
        return a->start < b->start;
    }
};

int main(void)
{
    int n, s, e;
    scanf("%d", &n);

    multiset<Line *, LineCompare> lines;

    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &s, &e);
        lines.insert(new Line(s, e));
    }
    //多新增一段長度為0的線段放在最後
    lines.insert(new Line(MAXM, MAXM));

    int count = 0;

    auto it = lines.begin();
    int start = (*it)->start;
    int end = (*it)->end;
    it++;

    for (it = it; it != lines.end(); it++)
    {
        //線段重疊或相連
        if ((*it)->start <= end)
        {
            end = max(end, (*it)->end);
        }
        //新線段
        else
        {
            //計算當前線段長度
            count += end - start;
            start = (*it)->start;
            end = (*it)->end;
        }
    }

    //印出解答
    printf("%d\n", count);

    //釋放記憶體
    for (it = lines.begin(); it != lines.end(); it++)
    {
        delete *it;
    }

    system("pause");
    return 0;
}

輸入:

4
5 6
1 2
4 8
7 9

5
160 180
150 200
280 300
300 330
190 210

1
120 120

輸出:

6

110

0

說明:
程式內使用 STL 的 multiset 集合來存放線段，multiset 內部使用紅黑樹來存放資料，所以再將線段加入集合時會自動排序，且因為有在泛型內加入 LineCompare，所以 multiset 會按照 LineCompare 重載的方法將線段按照 開始 位置 由小到大 排序。

接下來是此程式的重點，因為前面已經將所有線段排序過，所以每次的迴圈只會產生三種結果，重疊、相連、新線段，如下圖:

接著會將所有重疊或相連的線段合併，然後將合併完的線段長度加總就是解答。

合併的邏輯是依序將重疊或相連的線段合併，
遇到新線段時表示合併完成，將其加入結果，
再從新線段位置開始，繼續上面合併動作，直到跑完所有線段。

在合併線段時因為結束位置有可能小於或大於原線段，所以將結束位置取 max，圖中重疊的部分。

end = max(end, (*it)->end);

讀取完所有線段後，還要多加一段長度 0 的線段在最後，其用意在於，如果不加再合併完最後一段線段後，會來不及將此線段加入結果就會離開迴圈。

lines.insert(new Line(MAXM, MAXM));

參考文章:
APCS 105年3月題3-線段覆蓋長度(C++參考)

相關文章:
[C++][APCS] 成績指標
[C++][APCS] 矩陣轉換
[C++][APCS] 線段覆蓋長度