首次架設靜態網站，如有疏失，還請多多包涵。歡迎來信zhuastor@gmail.com

解題心得

一開始我想用二分搜尋找前後，結果一直RE
後來改成模擬並記錄前後的鄰居，結果TLE
只好乖乖看別人的題解，發現原來是我的lower_bound出錯
遞迴部份炸了，那我就乖乖地寫while迴圈QQ

解題想法

一個vector(不需要優先順序，用insert直接使他有優先順序性，由小到大)
一個lower_bound函式(解題主要關鍵)，至於結構加自定義sort就不另外講解
最開始我們先在vector裡面加入”0”跟”m”方便後面判斷
再來對於當前第一刀，我們提取結構中的ga[x].a(位置)
透過lower_bound找到第一個大於等於的元素位置
接著一連串判斷後插入(在此省略，這裡自己想會比較有幫助)
然後加總就好(習慣性加long long int ，int也會過喔)

非最佳解!好多人在0.1s之下，只是提供一種粗淺的解題方向

AC code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct job{
    int a,b;
};
job ga[200005];
vector<int> v;
bool cmp(job g,job t){
    return g.b<t.b;
}
int lower_bound(int left,int right,int pa){
    int mid;
    int pos;
    while(left<right){
        mid=(left+right)/2;
        if(v[mid]<pa){
            left=mid+1;
            pos=left;
        }
        else{
            right=mid;
            pos=right;
        }
    }
    return pos;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m;
    ll int sum=0;
    cin >> n >> m;
    for(int x=0;x<n;x++){
        cin >> ga[x].a >> ga[x].b;
    }
    sort(ga,ga+n,cmp);
    v.push_back(0);
    v.push_back(m);
    int k;
    for(int x=0;x<n;x++){
        k=lower_bound(0,v.size(),ga[x].a);
        if(k!=v.size() && ga[x].a!=m){
            if(v[k]==ga[x].a)
            sum+=v[k+1]-v[k-2];
            else{
                sum+=v[k]-v[k-1];
            }
        v.insert(v.begin()+k,ga[x].a);
        }
        else if(ga[x].a==m){
            sum+=v[v.size()-1]-v[v.size()-2];
        }
        // cout << sum << endl;
    }
    cout << sum << endl;
    return 0;
}

題目連結 : 2021年1月APCS 3.切割費用