# 資料結構題 - 切割費用 - APCS - by Peter Wang
## 題目資訊
此題為2021.1 測驗中的題目3
###### tags: `APCS`

## 題目敘述
有一根長度為 L 的棍子，你會把這個棍子切割 n 次。

假設一開始棍子左端放在數線上 0 的位置，棍子的右端放在數線上 L 的位置，每次的切割會給定一個介於 0 到 L 的數字表示要切個的位置，你要把穿過個這位置的棍子切成兩段，而所需的花費就等於所切割的棍子的長度。
### 輸入：
第一行有兩個整數 n,L。

接下來 n 行每行有兩個整數 x,i，表示 x 位置被切過一刀，而這刀是全部的切割中的第 i 刀，保證 i 是介於 [1,n] 的整數且不會重複。
### 輸出：
輸出一個整數表示總共的切割費用。

## 解題思路
利用set自動排序的特性，以及stl upper_bound的應用來完成此題。
如果有需要請觀看[upper_bound](https://hackmd.io/@PeterWang/B1ZKdjGlF)介紹。

## 程式碼

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int n,l;
vector <pair<int,int>> knife;

bool cmp(pair<int,int> a,pair<int,int> b){
  return a.second<b.second;
}

int main() {
  while(cin>>n>>l){
    for(int i=0;i<n;i++){
      int a,b;
      cin>>a>>b;
      knife.push_back({a,b});
    }
    sort(knife.begin(),knife.end(),cmp);
    long long ans=0;
    set <int> count;
    count.insert(0);
    count.insert(l);
    for(int i=0;i<n;i++){
      count.insert(knife[i].first);
      auto it=count.upper_bound(knife[i].first);
      it--;
      ans += *next(it)-*prev(it);
    }
    cout<<ans<<endl;
  }
}

## 資料來源
[zerojudge](https://zerojudge.tw/)
[題目敘述](https://zerojudge.tw/ShowProblem?problemid=f607)

## 備註
>[name=PeterWang]
>[time=Thu, Aug 12, 2021 8:29 PM]