【題解】ZeroJudge f607: 3. 切割費用

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=f607

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

int n, l;
long long ans;
set <int> st;
vector <pair<int, int> > v;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> l;
    st.insert(0);
    st.insert(l);
    for (int i = 0, a, b; i < n; i++){
        cin >> a >> b;
        v.push_back({b, a});
    }
    sort(v.begin(), v.end());
    for (auto [i, x]:v){
        st.insert(x);
        set<int>::iterator it = st.lower_bound(x);
        ans += (*next(it))-(*prev(it));
    }
    cout << ans << "\n";
}

如果IDE的編譯器不支援 auto 語法(C++ 11 以上版本的關鍵字,在編譯時自動推斷變數的資料型別),可以改用iterator。

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, l;
long long ans;
set <int> st;
vector <pair<int, int> > v;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> l;
    st.insert(0);
    st.insert(l);
    for (int i = 0, a, b; i < n; i++){
        cin >> a >> b;
        v.push_back({b, a});
    }
    sort(v.begin(), v.end());
    
    for (vector <pair<int, int> >::iterator it = v.begin(); it != v.end(); it++) {
        int x = (*it).second;
        st.insert(x);
        set<int>::iterator it_set = st.lower_bound(x);
        ans += (*next(it_set))-(*prev(it_set));
    }
    cout << ans << "\n";
}
分享本文 Share with friends