# **2016 3月 APCS 實作三 線段覆蓋長**
:::warning
題目:
給定一維座標上一些線段，求這些線段所覆蓋的長度，注意，重疊的部分只能算一次。
例如給定 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標頭檔**
```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
:::
Sign in with Wallet
Connect another wallet