二叉堆

//POJ 2010
//题目概述：数学题，状态转移
//二叉堆的应用，卡排序，BBS()过不了
//这个AC异常艰辛 总共提交11次 充分体现了锲而不舍的精神
//AC 2016-10-15

#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXC 100000 + 10
#define MAXN 20000 + 10

struct node{
    int val, cost;
    friend bool operator < (const node &n1, const node &n2){
        return n1.val < n2.val;
    }
    friend bool operator > (const node &n1, const node &n2){
        return n1.val > n2.val;
    }
}p[MAXC];

struct BHeap{
    node heap[MAXC];
    int n;
    BHeap(): n(0){}
    void clear(){n = 0;}
    void down(int i){
        for (int j = i * 2; j <= n; j *= 2){
            j += (j < n) && (heap[j].cost < heap[j + 1].cost);
            if (heap[j].cost > heap[i].cost){
                swap(heap[i], heap[j]);
                i = j;
            }
            else break;
        }
    }
    void up(int i){
        for (int j = i / 2; j >= 1; j /= 2){
            if (heap[j].cost < heap[i].cost){
                swap(heap[i], heap[j]);
                i = j;
            }
            else break;
        }
    }
    node &pop(){
        swap(heap[1], heap[n--]);
        down(1);
        return heap[n + 1];
    }
    node &top(){
        return heap[1];
    }
    void push(node &a){
        heap[++n] = a;
        up(n);
    }
}heap;
int before[MAXC], after[MAXC];

int main(){
    int n, c, f, minval = 0x7f7f7f7f;
    freopen("fin.c", "r", stdin);
    while (scanf("%d%d%d", &n, &c, &f) + 1){
	    for (int i = 1; i <= c; i++){
	        scanf("%d%d", &p[i].val, &p[i].cost);
	    }
	    sort(p + 1, p + 1 + c);
	    int size = n / 2;

	    heap.clear();
	    before[size + 1] = 0;
	    for (int i = 1; i <= size; i++){
	        heap.push(p[i]);
	        before[size + 1] += p[i].cost;
	    }
	    for (int i = size + 1; i < c - size; i++){
	        if (heap.top().cost > p[i].cost){
	            before[i + 1] = before[i] - heap.pop().cost + p[i].cost;
	            heap.push(p[i]);
	        }
	        else before[i + 1] = before[i];
	    }

	    heap.clear();
	    after[c - size] = 0;
	    for (int i = c; i > c - size; i--){
	        heap.push(p[i]);
	        after[c - size] += p[i].cost;
	    }
	    for (int i = c - size; i > size + 1; i--){
	        if (heap.top().cost > p[i].cost){
	            after[i - 1] = after[i] - heap.pop().cost + p[i].cost;
	            heap.push(p[i]);
	        }
	        else after[i - 1] = after[i];
	    }
	    for (int i = c - size; i >= size + 1; i--){
	        if (after[i] + before[i] + p[i].cost <= f){
	            printf("%d\n", p[i].val);
	            goto END;
	        }
	    }
        puts("-1"); END:;
    }
}