APCS線段覆蓋長

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

第一列是一個正整數 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標頭檔

#include <iostream>
#include <vector> //vector
using namespace std;

---

宣告題目需要的變數

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); //將x元素放進A陣列裡(接在上一個元素後面)
      if(x>max)//找全部線段裡最遠的點(max)
      max = x;
}

重複2n次是因為一條繩子有兩個端點，n條就是2*n個端點( A[ 0 ] , A[ 1 ]為第一條繩子的兩端點，A[ 2 ] , A[ 3 ]為第二條繩子兩端點…)

並在過程中就找出最大值

---

宣告一個大小為max的陣列(A1)，並把每一格都設成-1

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;
         }
    }

外層迴圈 : A[ i ]為每條線段左邊的端點(所以才是i+=2)

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

這樣即使有覆蓋的地方就會保持1不變了

---

接著用一個for跑完整條繩子，如果A1[ i ]是1那就把ans+1

for(int i=0;i<=max;i++)
{
    if(A1[i]==1)
    ans++;
}
cout << ans;

最後輸出ans

---

完整程式碼

#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;
}

掰掰 :D