2021/1/9 切割費用

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)

相關文章

分享此文：