题目链接

Moo University - Financial Aid POJ - 2010

思路

$$ \begin{aligned}本题网上有二分做法，笔者认为二分好像不正确，并且枚举的复杂的就是nlogn为何要二分呢？\\\\先用大根堆预处理每个牛为中位数时左右两端学费的最小值。\\\\然后遍历一边判断一下答案。\end{aligned} $$

时间复杂度

$$ O(Nlog(N)) $$

代码

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

using namespace std;

const int MAXN = 1e5 + 10;

int a[MAXN], b[MAXN], id[MAXN];
long long lx[MAXN], rx[MAXN];

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

int main() {
    int n, c, f;
    scanf("%d%d%d", &n, &c, &f);// don't forget &

    for (int i = 1; i <= c; i++) {
        scanf("%d%d", &a[i], &b[i]);// don't forget &
        id[i] = i;
    }

    sort(id + 1, id + 1 + c, cmp);

    int l = n / 2 + 1;
    int r = c - n / 2;

    priority_queue<int> bg;
    for (int i = 1; i <= c; i++) {
        int x = id[i];
        bg.push(b[x]);
        lx[i] = lx[i - 1] + b[x];
        if ((int)bg.size() > n / 2) {
            lx[i] -= bg.top();
            bg.pop();
        }
    }
    while (!bg.empty()) {
        bg.pop();
    }
    for (int i = c; i >= 1; i--) {
        int x = id[i];
        bg.push(b[x]);
        rx[i] = rx[i + 1] + b[x];
        if ((int)bg.size() > n / 2) {
            rx[i] -= bg.top();
            bg.pop();
        }
    }
    int ans = -1;
    for (int i = r; i >= l; i--) {
        int x = id[i];
        if (lx[i - 1] + rx[i + 1] + b[x] <= f) {
            ans = a[x];
            break;
        }
    }
    printf("%d", ans);
    return 0;
}