# APCS實作題2021年1月第3題：切割費用
> 日期：2024年7月10日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=f607)
## 題目
### 問題描述
有一根長度為 $L$ 的棍子，你會把這個棍子切割 $n$ 次。
假設一開始棍子左端放在數線上 $0$ 的位置，棍子的右端放在數線上 $L$ 的位置，每次的切割會給定一個介於 $0$ 到 $L$ 的數字表示要切個的位置，你要把穿過個這位置的棍子切成兩段，而所需的花費就等於所切割的棍子的長度。
<br />
### 輸入說明
第一行有兩個整數 $n, L$。
接下來 $n$ 行每行有兩個整數 $x, i$，表示 $x$ 位置被切過一刀，而這刀是全部的切割中的第 $i$ 刀，保證 $i$ 是介於 $[1, n]$ 的整數且不會重複。
配分
- 20分：$1 \leq n \leq 1000,~ 1 \leq L \leq 10^7$
- 30分：$1 \leq n \leq 50000,~ 1 \leq L \leq 10^7$
- 50分：$1 \leq n \leq 200000,~ 1 \leq L \leq 10^7$
<br />
### 輸出格式
輸出一個整數表示總共的切割費用，答案可能超過 $2^{31}$ 但不會超過 $2^{60}$。
<br />
### 範例輸入
```
3 7
2 2
3 1
5 3
```
### 範例輸出
```
14
```
<br />
## Python 程式碼
### 寫法1，由 x 向左、右掃過找已切割的點
第10筆測資會超時。
```python=
n, L = map(int, input().split()) # 讀取切割次數 n、棍子長度 L
data = [] # 儲存資料用的容器
for _ in range(n): # 讀取 n 行資料，用數組 (x, i) 放入串列 data
data.append(tuple(map(int, input().split())))
data.sort() # 依照 x 由小到大排序
ans = 0 # 答案，預設為 0
for j, (x, i) in enumerate(data): # 依序讀取 data 的資料，索引值為 j
left = 0 # x 的左側已切割位置，預設為 0
right = L # x 的右側已切割位置，預設為 L
for k in range(j-1, -1, -1): # 由 j-1 開始向左掃過
if data[k][1] < i: # 如果 data[k] 已切割
left = data[k][0] # 找到 left
break
for k in range(j+1, n): # 由 j+1 開始向右掃過
if data[k][1] < i: # 如果 data[k] 已切割
right = data[k][0] # 找到 right
break
ans += right - left # 更新 ans
print(ans) # 印出 ans
```
<br /><br />
### 寫法2，使用 bisect 函式庫
費時最久約為 1.3 s，使用記憶體最多約為 32.9 MB，通過測試。
```python=
from bisect import bisect_left, insort
n, L = map(int, input().split()) # 讀取切割次數 n、棍子長度 L
data = [] # 儲存資料用的容器
for _ in range(n): # 讀取 n 行資料，用數組 (i, x) 放入串列 data
x, i = map(int, input().split())
data.append((i, x))
data.sort() # 依照 i 由小到大排序
pos = [0, data[0][1], L] # 已切割的位置，包含兩端 0、L
ans = L # 跳過第1個切割點，答案預設為 L
for i, x in data[1:]: # 依序讀取 data[1] ~ data[-1]
insort(pos, x) # 引用 bisect_insort，於 pos 中插入 x
j = bisect_left(pos, x) # 於 pos 中找 x 的索引值
left = pos[j-1] # x 左側切割點
right = pos[j+1] # x 右側切割點
ans += right - left # 更新 ans
print(ans) # 印出 ans
```
修改一下第14、15行，刪掉 insort，少做一次二分搜尋法，但是花費時間相差不多，最久約為 1.2 s，使用記憶體最多約為 32.9 MB，通過測試。
```python=
from bisect import bisect_left, insort
n, L = map(int, input().split()) # 讀取切割次數 n、棍子長度 L
data = [] # 儲存資料用的容器
for _ in range(n): # 讀取 n 行資料，用數組 (i, x) 放入串列 data
x, i = map(int, input().split())
data.append((i, x))
data.sort() # 依照 i 由小到大排序
pos = [0, data[0][1], L] # 已切割的位置，包含兩端 0、L
ans = L # 跳過第1個切割點，答案預設為 L
for i, x in data[1:]: # 依序讀取 data[1] ~ data[-1]
j = bisect_left(pos, x) # 於 pos 中找插入 x 的索引值
pos.insert(j, x) # 於 pos 中插入 x
left = pos[j-1] # x 左側切割點
right = pos[j+1] # x 右側切割點
ans += right - left # 更新 ans
print(ans) # 印出 ans
```
<br /><br />
## C++ 程式碼
### 寫法1，由 x 向左、右掃過找已切割的點
程式運作邏輯與 Python 程式碼寫法1相同。儲存 n, L, ans 的變數格式如果使用 int，從第10筆測資開始會溢位，改用 long long 才能通過測試。費時最久約為 0.5 s，使用記憶體最多約為 3.4 MB，通過測試。
```cpp=
#include <iostream>
#include <algorithm>
#include <utility>
typedef long long LL;
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0); // 加速
LL n, L; cin >> n >> L; // 讀取切割次數 n、棍子長度 L
pair<LL, LL> data[n]; // 儲存資料用的容器
for(LL i=0; i<n; i++) cin >> data[i].first >> data[i].second; // 讀取 n 行資料，用 pair (x, i) 放入陣列 data
sort(data, data+n); // 依照 x 由小到大排序
LL ans = 0; // 答案，預設為0
for(LL j=0; j<n; j++) { // 依序讀取 data 的資料，索引值為 j
LL x = data[j].first, i = data[j].second; // 第i次切割點位置 x
LL left = 0, right = L; // x 的左側已切割位置，預設為 0；x 的右側已切割位置，預設為 L
for(LL k=j-1; k>=0; k--) { // 由 j-1 開始向左掃過
if (data[k].second < i) { // 如果 data[k] 已切割
left = data[k].first; // 找到 left
break;
}
}
for(LL k=j+1; k<n; k++) { // 由 j+1 開始向右掃過
if (data[k].second < i) { // 如果 data[k] 已切割
right = data[k].first; // 找到 right
break;
}
}
ans += right - left; // 更新 ans
}
cout << ans << "\n"; // 印出 ans
return 0;
}
```
<br /><br />
### 寫法2，使用 lower_bound
程式運作邏輯與 Python 程式碼寫法2相同。儲存 n, L, ans 的變數格式如果使用 int，從第10筆測資開始會溢位，改用 long long 才能通過測試。費時最久約為 0.1 s，使用記憶體最多約為 7.9 MB，通過測試。
```cpp=
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
typedef long long LL;
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0); // 加速
LL n, L; cin >> n >> L; // 讀取切割次數 n、棍子長度 L
pair<LL, LL> data[n]; // 儲存資料用的容器
for(LL i=0; i<n; i++) cin >> data[i].second >> data[i].first; // 讀取 n 行資料，用 pair (i, x) 放入陣列 data
sort(data, data+n); // 依照 i 由小到大排序
vector<LL> pos = {0, data[0].second, L}; // 切割點位置，包含兩端 0、L
LL ans = L; // 略過第1個切割點，答案預設為L
for(LL j=1; j<n; j++) { // 依序讀取 data[1] ~ data[n-1] 的資料，索引值為 j
LL i = data[j].first, x = data[j].second; // 第i次切割點位置 x
auto it = lower_bound(pos.begin(), pos.end(), x); // 找到於 pos 中插入 x 的位址
pos.insert(it, x); // 於 pos 中插入 x
LL idx = lower_bound(pos.begin(), pos.end(), x) - pos.begin(); // 找到 x 於 pos 中的索引值
LL left = pos[idx-1], right = pos[idx+1]; // x 的左、右兩側已切割位置
ans += right - left; // 更新 ans
}
cout << ans << "\n"; // 印出 ans
return 0;
}
```
```cpp=
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
typedef long long LL;
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0); // 加速
LL n, L; cin >> n >> L; // 讀取切割次數 n、棍子長度 L
pair<LL, LL> data[n]; // 儲存資料用的容器
for(LL i=0; i<n; i++) cin >> data[i].second >> data[i].first; // 讀取 n 行資料，用 pair (i, x) 放入陣列 data
sort(data, data+n); // 依照 i 由小到大排序
vector<LL> pos = {0, data[0].second, L}; // 切割點位置，包含兩端 0、L
LL ans = L; // 略過第1個切割點，答案預設為L
for(LL j=1; j<n; j++) { // 依序讀取 data[1] ~ data[n-1] 的資料，索引值為 j
LL i = data[j].first, x = data[j].second; // 第i次切割點位置 x
LL idx = lower_bound(pos.begin(), pos.end(), x) - pos.begin(); // 找到於 pos 中插入 x 的位址
pos.insert(pos.begin()+idx, x); // 於 pos 中插入 x
LL left = pos[idx-1], right = pos[idx+1]; // x 的左、右兩側已切割位置
ans += right - left; // 更新 ans
}
cout << ans << "\n"; // 印出 ans
return 0;
}
```
<br /><br />
---
###### tags:`APCS`、`Python`、`C++`
Sign in with Wallet
Connect another wallet