POJ 2010 Moo University – Financial Aid（堆维护滑窗kth，二分）

按照score排序，贪心，从左到右用堆维护并且记录前面的最小N/2个花费之和。

然后从右向左枚举中位数，维护N/2个数之和加上并判断是否满足条件。（stl的队列没有clear(),只能一个一个pop…

复杂度O(nlogn)

也可以二分。先按照score排序，记录备份牛在排序后的下标。然后将备份按照资金排序，

，二分中位数的值，对于mid值，按照备份顺序贪心选择牛，根据之前的下标判断在左边或者右边。

因为是最贪心的选，如果两边都不够，说明无解。如果某一边少了，mid就应该往相反的方向移动。

如果满足条件就记录答案，并向上缩小区间。

复杂度也是O(nlogn)

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
//#include<bits/stdc++.h>
using namespace std;#define PB push_back
#define MP make_pair
#define fi first
#define se second
#define PS pushconst int maxn = 1e5+;
const int maxsz = 1e4+;
struct BinaryHEAP
{
    int Heap[maxsz];
    int sz;
    #define Cmp(a,b) ((a)>(b))
    void push(int x)
    {
        int i = ++sz;
        while(i > ){
            int p = i>>;
            if(!Cmp(x,Heap[p])) break;
            Heap[i] = Heap[p];
            i = p;
        }
        Heap[i] = x;
    }    void pop()
    {
        int x = Heap[sz--];
        int i = ;
        while((i<<)<=sz){
            int a = i<<, b = i<<|;
            if(b<=sz && Cmp(Heap[b],Heap[a])) a = b;
            if(!Cmp(Heap[a],x)) break;
            Heap[i] = Heap[a];
            i = a;
        }
        Heap[i] = x;
    }
    int top(){ return Heap[]; }
    //int operator[](int x){ return Heap[x]; }
}q;pair<int,int> cow[maxn];
int N, C, F;
int Half;
int preSum[maxn];int sol()
{
    sort(cow,cow+C);
    int Half = N>>, sum = ;
    for(int i = ; i < Half; i++) {
        sum += cow[i].se;
        q.push(cow[i].se);
    }
    for(int i = Half; i < C-Half; i++){
        preSum[i] = sum;
        if(q.top() > cow[i].se) {
            sum -= q.top();
            q.pop();
            sum += cow[i].se;
            q.push(cow[i].se);
        }    }
    q.sz = ;
    sum = ;
    for(int i = C-Half; i < C; i++) {
        sum += cow[i].se;
        q.push(cow[i].se);
    }
    for(int i = C-Half; --i >= Half; ){
        if(sum + preSum[i] + cow[i].se <= F) return cow[i].fi;
        if(q.top() > cow[i].se) {
            sum -= q.top();
            q.pop();
            sum += cow[i].se;
            q.push(cow[i].se);
        }
    }
    return -;
}//#define LOCAL
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif    scanf("%d%d%d",&N,&C,&F);
    for(int i = ; i < C; i++){
        scanf("%d%d",&cow[i].fi,&cow[i].se);
    }
    printf("%d\n",sol());
    return ;
}