---
# System prepended metadata

title: ZeroJudge f607. 切割費用
tags: [ZeroJudge, APCS, C++]

---

# ZeroJudge f607. 切割費用
[f607. 切割費用 (題目連結)](https://zerojudge.tw/ShowProblem?problemid=f607)
## 解題思路
要求每一刀的切割費用只須尋找切割順序( i )小於本身，且切割位置( x )最接近本身的兩刀即可。

使用`pair<int, int>`將資料做儲存( first 存 x ，second 存 i )，再將被切的位置由小到大作排列。  
## 程式碼
<font color="#00CE17">**AC**</font> **(0.8s, 3.4MB)**
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, len;
	cin>>n>>len;
	pair<int, int> d[n];
	for(int i=0; i<n; i++) cin>>d[i].first>>d[i].second;
	sort(d, d + n);
	int ans = 0;
	for(int i=0; i<n; i++){
		int l = 0, r = len;
		for(int j=i-1; j>=0; j--){
			if(d[i].second > d[j].second && d[i].first > d[j].first){
				l = d[j].first;
				break;
			}
		}
		for(int j=i+1; j<n; j++){
			if(d[i].second > d[j].second && d[i].first < d[j].first){
				r = d[j].first;
				break;
			}
		}
		ans += r - l;
	}
	cout<<ans;
	
	return 0;
} 
```
###### 闕以諾 2022/7/7
###### tags: `C++` `ZeroJudge` `APCS`
