题目链接

Expedition POJ - 2431

思路

$$ \begin{aligned}仔细读题，弄清变量。\\\\把可选的加油站加入大根堆，需要的时候就取个最大的。\end{aligned} $$

时间复杂度

$$ O(Nlog(N)) $$

代码

#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

const int MAXN = 1e4 + 10;

int a[MAXN], b[MAXN], id[MAXN];

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

int main() {
    int n;
    scanf("%d", &n);// don't forget &
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i], &b[i]);// don't forget &
        id[i] = i;
    }
    int l, p;
    scanf("%d%d", &l, &p);// don't forget &
    for (int i = 1; i <= n; i++) {
        a[i] = l - a[i];
    }
    sort(id + 1, id + 1 + n, cmp);
    int cur = p;
    priority_queue<int> bg;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int x = id[i];
        if (cur >= l) {
            break;
        }
        while (bg.size() != 0 && cur < a[x]) {
            cur += bg.top();
            ans++;
            bg.pop();
        }
        if (cur < a[x]) {
            break;
        }
        bg.push(b[x]);
    }
    if (cur < l) {
        while (bg.size() != 0 && cur < l) {
            cur += bg.top();
            ans++;
            bg.pop();
        }
        if (cur < l) {
            ans = -1;
        }
    }
    printf("%d", ans);
    return 0;
}