---
# System prepended metadata

title: APCS線段覆蓋長
tags: [APCS, 解析]

---

# **APCS線段覆蓋長**
:::warning
題目:
給定一維座標上一些線段，求這些線段所覆蓋的長度，注意，重疊的部分只能算一次。
例如給定 4 個線段：(5, 6)、(1, 2)、(4, 8)、(7, 9)，如下圖，線段覆蓋長度為 6 。

![image.png](https://hackmd.io/_uploads/H1Ert-vma.png)

第一列是一個正整數 N ，表示此測資有 N 個線段。
接著的 N 列每一列是一個線段的開始端點座標整數值 L 和結束端點座標整數值 R ，開始端點座標值小於等於結束端點座標值，兩者之間以一個空格區隔。


其中  30%的測資滿足， N < 100 ， 0 ≤ L , R < 1000 ，並且線段沒有重疊。
其中  70%的測資滿足， N < 100 ， 0 ≤ L , R < 1000 ，並且線段可能重疊。
其中100%的測資滿足， N < 10000 ， 0 ≤ L , R < 10000000 ，並且線段可能重疊。
https://zerojudge.tw/ShowProblem?problemid=b966
:::
這題我用到 ==vector動態陣列==做，並找出所有線段裡最遠的點(max)，以它為基準把他想像成一個箱子(長度為max)，然後把繩子都疊上去
******
**首先引入vector標頭檔**
```cpp=
#include <iostream>
#include <vector> //vector
using namespace std;
```
***
**宣告題目需要的變數**
```cpp=
vector <int> A; //儲存每條繩子兩端點的陣列
int n, ans=0, max=0;
```
***
**輸入**
```cpp=
cin >> n;
for(int i=0;i<2*n;i++)
{
      int x;
      cin >> x;
      A.push_back(x); //將x元素放進A陣列裡(接在上一個元素後面)
      if(x>max)//找全部線段裡最遠的點(max)
      max = x;
}
```
重複2n次是因為一條繩子有兩個端點，n條就是2*n個端點( A[ 0 ] , A[ 1 ]為第一條繩子的兩端點，A[ 2 ] , A[ 3 ]為第二條繩子兩端點...)

並在過程中就找出最大值
***
**宣告一個大小為max的陣列(A1)，並把每一格都設成-1**
```cpp=
vector <int> A1 (max, -1);
```
***
**開始把每條繩子都放在新陣列裡**
``` cpp=
for(int i=0;i<=2*n;i+=2)
    {
         for(int j=A[i];j<A[i+1];j++)
         {
            A1[j] = 1;
         }
    }
```
==外層迴圈== : A[ i ]為每條線段左邊的端點(所以才是i+=2)

==內層迴圈== : j把每條繩子左邊端點( A[ i ] ) 到 右邊端點( A[ i + 1 ] )設成1

這樣即使有覆蓋的地方就會保持1不變了
***
接著用一個for跑完整條繩子，如果A1[ i ]是1那就把ans+1
```cpp=
for(int i=0;i<=max;i++)
{
    if(A1[i]==1)
    ans++;
}
cout << ans;
```
最後輸出ans
***
:::success
完整程式碼
:::
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main()
{    
    vector <int> A;
    int n,ans=0,max=0;
    cin >> n;
    for(int i=0;i<2*n;i++)
    {
       int x;
       cin >> x;
       A.push_back(x);
       if(x>max)
       max = x;
    }
    vector <int> A1 (max, -1);
    for(int i=0;i<=2*n;i+=2)
    {
         for(int j=A[i];j<A[i+1];j++)
         {
            A1[j]=1;
         }
    }
    for(int i=0;i<=max;i++)
    {
        if(A1[i]==1)
        ans++;
    }
    cout << ans;
    return 0;
}
```
:::success
掰掰 :D
:::