[題解]APCS切割費用

110/01 實作題第三題切割費用

這一題雖然在考試中有想到利用二元樹的方法，於是開了一個陣列儲存樹的節點（前段時間寫了一些線段樹，所以用了這個方法！）但我沒有注意到這不是一棵完滿二元樹，不會平衡啊！把範例測資丟上去對了，結果半分都沒有拿到:cry:，以後必須注意！
用std::set搭配 next(),prev() 指標，找出鄰近的切割點之差，就可以AC了！

在 set 中使用insert() 函式會回傳pair 在使用的時候要變成：

1	auto pos = s.insert(arr[i]).first;

這是考試送出的0分程式碼

#include <bits/stdc++.h>
#define int long long
#define ios ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
int n,L,ans = 0;
int seg[1000000] = {0};

void build(int val,int cur){
    if(seg[cur]==0){
        seg[cur] = val;
        return;
    }
    if(val>seg[cur])build(val, 2*cur+2);
    else build(val, 2*cur+1);
}//建立一個會爆掉的二元樹
void func(int val,int cur){
    int up = L,low = 0;
    if(seg[cur]==val){
        ans+=up-low;
        return;
    }
    while(seg[cur]!=val){
        if(val>seg[cur]){
            low = seg[cur];
            cur = 2*cur+2;
        }
        else{
            up = seg[cur];
            cur = 2*cur+1;
        }
    }
    ans+=up-low;
}

signed main(){
    ios;    
    cin>>n>>L;
    int arr[n];
    for(int i=0;i<n;i++){
        int a,b;cin>>a>>b;
        arr[b-1] = a;
    }
    for(int i=0;i<n;i++)build(arr[i], 0);
    for(int i=0;i<n;i++)func(arr[i], 0);
    cout<<ans<<endl;
}

這是正解：

#include <bits/stdc++.h>
#define int long long
#define ios ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
int n,l,arr[200000];

signed main(){
    ios;
    cin>>n>>l;
    set<int> s = {0,l};
    for(int i=0;i<n;i++){
        int ind,pos;cin>>pos>>ind;
        arr[ind-1] = pos;
    }
    int ans = 0;
    for(int i=0;i<n;i++){
        auto pos = s.insert(arr[i]).first;
        ans+= *next(pos)- *prev(pos);
    }
    cout<<ans<<endl;
}

110/01 實作題第三題 切割費用

110/01 實作題第三題切割費用