[C++][APCS] 线段覆盖长度

题目出自 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;}

输入:

45 61 24 87 9

5160 180150 200280 300300 330190 210

1120 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] 线段覆盖长度