Moo University - Financial Aid（优先队列）

Moo University - Financial Aid（优先队列）

Moo University - Financial Aid - POJ 2010 - Virtual Judge

先预处理出对于（n-1）/2个牛里来说，第i头牛左边sum最小值和右边sum最小值，利用优先队列的大根堆，把左边或者右边占用值最大的减去，这样左右两边仍然是对称的，只是对值大的牛进行了选择，而且选择时是不包括第i头牛，所以最后判断的时候需要左边记录的值加上右边记录的值再加上第i头牛的值如果小于f，则可以输出答案了，记得遍历的时候从大到小i--，否则输出的则是符合要求的最小的中位数

AC代码：

#include 
using namespace std;
typedef long long ll;
const int maxn=100010;
int n,c;
ll f,L[maxn],R[maxn];
struct node
{
    ll c,f;
}q[maxn];
bool cmp(node a,node b)
{
    if(a.c==b.c)
    return a.fp;
    ll sum=0;
    for(int i=0;i=0;i--)
    {
        if(i>c-1-n/2)
        {
            p.push(q[i].f);
            sum+=q[i].f;
        }
        else
        {
            R[i]=sum;
            sum+=q[i].f;
            p.push(q[i].f);
            sum-=p.top();
            p.pop();
        }
    }
}
bool ok(int t)
{
    return L[t]+R[t]+q[t].f<=f;
}
int main()
{
    while(scanf("%d%d%lld",&n,&c,&f)!=EOF)
    {
        for(int i=0;i=n/2;i--)
        {
            if(ok(i))
            {
                ans=i;
                break;
            }
        }
        if(ans!=-1)
        printf("%lldn",q[ans].c);
        else
        printf("-1n");
    }
    return 0;
}