C++ APCS實作題 2021/1 3 : 切割費用

用到了 set 和 iterator

#include<bits/stdc++.h>
using namespace std;

struct data{
    int x,i;
};
data dt[200000];


bool cmp(data a,data b){
    return a.i<b.i;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;int L;
    cin>>n>>L;
    for(int i=0;i<n;i++){
	cin>>dt[i].x;
	cin>>dt[i].i;
    }
    sort(dt,dt+n,cmp);

    
    set<int> s;
    s.insert(0);
    s.insert(L);
    long long sum=0;
    set<int>::iterator ptrE=s.begin();
    set<int>::iterator ptrB=s.end();
    for(int i=0;i<n;i++){
	s.insert(dt[i].x);
	ptrE=s.lower_bound(dt[i].x);
	
	ptrE--;
	ptrB=ptrE;
	ptrE++;ptrE++;
	//cout<<(*ptrE)<<" "<<(*ptrB)<<"\n";
	sum+= (*ptrE)-(*ptrB); 
    }
    cout<<sum;
    return 0;
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *