2023.1.11 PM 09:00 by CBJ
來源 : https://zerojudge.tw/ShowProblem?problemid=f607 出題者 : 2021年1月APCS 標籤 : 二分搜尋法、C++ set 難易度 : 3
解題想法 : 假如切下一刀,如何找出棍子左右端點? 首先可以得知,每個陣列位置(index)絕對是按照順序(這是一定的),因此當切在x處的時候,我們可以保證左邊絕對比x小,右邊絕對比x大,想到這裡,應該就可以發現二分搜尋的點。 我們使用point(C++使用set型態,Python使用list)紀錄已經切過的點,第一步先將左界0和右界L丟進point,然後對於每次的新切點,先將新切點丟進point並維持排序狀態(C++使用set.insert(),Python使用bisect.insort()),然後除了新切點為0或L之外,(C++/Python)左邊可以使用(set.lower_bound()/bisect.bisect_left())先找到第一個「大於等於」新切點的值,但由於我們已經先將新切點丟入point,所以那個值一定會是新切點,如此一來,只要取他的前一個就會是第一個小於point的值。取右邊則比較單純,只要使用(set.upper_bound(),bisect.bisect_bisect.right())取得第一個「大於」新切點的值就會是右邊,而(右邊-左邊)就是所求的花費。 最後輸出所有花費的總和,若是C++請記得開long long。
//C++ language
#include<iostream>
#include<set> //set
#include<vector> //vector
#include<utility> //pair
#include<algorithm> //sort()
using namespace std;
int main(){
int n,L; cin>>n>>L;
set<int>point;
point.insert(0); point.insert(L);
vector<pair<int,int>>cut;
for(int i=0;i<n;i++){
int x,y; cin>>x>>y;
cut.push_back({y,x}); //y,x not x,y
}
sort(cut.begin(),cut.end());
long long cost=0;
for(pair<int,int>p: cut){
int i=p.second,left,right;
point.insert(i);
if(i==0) left=0;
else left=*prev(point.lower_bound(i));
if(i==L) right=L;
else right=*point.upper_bound(i);
cost+=(right-left);
}
cout<<cost<<"\n";
return 0;
}

## Python language
from bisect import bisect_left as lower_bound
from bisect import bisect_right as upper_bound
from bisect import insort
n,L=map(int,input().split())
point=[0,L]
cut=[]
for j in range(n):
x,i=map(int,input().split())
cut.append([i,x])
cut.sort()
cost=0
for _,i in cut:
insort(point,i)
if i==0: left=0
else: left=point[lower_bound(point,i)-1]
if i==L: right=L
else: right=point[upper_bound(point,i)]
cost+=right-left
print(cost)
