【題解】ZeroJudge e877: Q2 湖畔大樓

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

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

int t, n, a[100005], h[100005], l[100005];

bool cmp(int x, int y){
    return l[x] < l[y];
}

int main() {
    cin >> t;
    while (t--){
        cin >> n;
        for (int i = 0; i < n; i++){
            cin >> h[i] >> l[i];
            a[i] = i;
        }
        int ans = 0, tot = 0;
        sort(a, a+n, cmp);
        multiset <int> st;
        for (int i = 0; i < n; i++){
            if (l[a[i]] >= tot){
                tot += h[a[i]];
                st.insert(h[a[i]]);
                ans++;
            }
            else{
                if (h[a[i]] < *(--st.end())){
                    tot -= *(--st.end());
                    st.erase(--st.end());
                    tot += h[a[i]];
                    st.insert(h[a[i]]);
                }
            }
        }
        cout << ans << "\n";
    }
}
分享本文 Share with friends