ZeroJudge f607. 切割費用

f607. 切割費用 (題目連結)

解題思路

要求每一刀的切割費用只須尋找切割順序( i )小於本身，且切割位置( x )最接近本身的兩刀即可。

使用pair<int, int>將資料做儲存( first 存 x ，second 存 i )，再將被切的位置由小到大作排列。

程式碼

AC (0.8s, 3.4MB)

#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