切棍子

#include <bits/stdc++.h>

using namespace std;

struct pos{
    int pos;
    int th;
};

bool cmp(pos a,pos b){
    return a.th<b.th;
}

void print(vector<int> v){
    for(int i=0;i<v.size();i++) cout<<v[i]<<" ";
    cout<<endl;
}

int main()
{
    long long int n,L,sum=0;
    cin>>n>>L;
    vector<pos> cut(n);
    vector<int> log;
    for(int i=0;i<n;i++){
        cin>>cut[i].pos>>cut[i].th;
    }
    sort(cut.begin(),cut.end(),cmp);
    log.push_back(0);
    log.push_back(L);
    vector<int>::iterator low;
    for(int i=0;i<cut.size();i++){
        low=lower_bound(log.begin(),log.end(),cut[i].pos);
        //cout<<*low<<" "<<*(low-1)<<endl;
        //print(log);
        sum+=*low-*(low-1);
        log.insert(low,cut[i].pos);
    }
    cout<<sum<<endl;
    return 0;
}

2021-11-25更新set做法

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int N,L,sum=0;
    cin>>N>>L;
    set<int> s={0,L};
    pair<int,int> p[N];
    for(int i=0;i<N;i++){
        cin>>p[i].second>>p[i].first;
    }
    sort(p,p+N);
    for(int i=0;i<N;i++){
        s.insert(p[i].second);
        auto it=s.find(p[i].second);
        sum+=*next(it)-*prev(it);
    }
    cout<<sum;
    return 0;
}