本文主要是介绍POJ2010 Moo University - Financial Aid，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：奶牛学校招生，c头奶牛报名，要选n头（n为奇数），学校是义务制，所以每头奶牛的学费都由学校负责。每头奶牛都由自己的考试分数和它需要花的学费，学校总共有f的资金，问合法招生方案中中间分数（即排名第(n+1)/2）最高的是多少。
题解：先将所有的奶牛按照分数由高到低排序，假设k是招的奶牛中排名中间的那头，按照排序可知，[1,k-1]中的奶牛必定被招了(n-1)/2头，[k+1,c]中也必定被招了(n-1)/2头，而且无论招的是谁，分数是怎么样，最后影响结果的都只是k的分数。于是，可以预处理dpl[i]代表[1,i]头牛中选出(n-1)/2头牛的最小花费，dpr[i]代表[i,c]头牛中选出(n-1)/2头牛的花费，预处理方法可以用一个大顶堆，复杂度nlogn，最后枚举中间牛复杂度n。
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN=111111;
priority_queue<int> Q;
int dpl[MAXN];
int dpr[MAXN];
struct eg
{int a,b;
}cow[MAXN];
bool cmp(const eg&a,const eg&b)
{if(a.a!=b.a)return a.a>b.a;return a.b<b.b;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("G:/1.txt","r",stdin);freopen("G:/2.txt","w",stdout);#endifint n,c,f;scanf("%d%d%d",&n,&c,&f);for(int i=1;i<=c;i++)scanf("%d%d",&cow[i].a,&cow[i].b);sort(cow+1,cow+c+1,cmp);int nu=(n-1)/2;int sum=0;for(int i=1;i<=nu;i++){Q.push(cow[i].b);sum+=cow[i].b;}dpl[nu]=sum;for(int i=nu+1;i<=c;i++){if(cow[i].b>Q.top()){dpl[i]=sum;}else{sum=sum-Q.top()+cow[i].b;Q.pop();Q.push(cow[i].b);dpl[i]=sum;}}sum=0;while(!Q.empty())Q.pop();for(int i=c;i>=c-nu+1;i--){Q.push(cow[i].b);sum+=cow[i].b;}dpr[c-nu+1]=sum;for(int i=c-nu;i>=1;i--){if(cow[i].b>Q.top()){dpr[i]=sum;}else{sum=sum-Q.top()+cow[i].b;Q.pop();Q.push(cow[i].b);dpl[i]=sum;}}bool flag=false;for(int i=nu+1;i<=c-nu;i++){if(cow[i].b+dpl[i-1]+dpr[i+1]<=f){flag=true;printf("%d\n",cow[i].a);break;}}if(!flag)printf("-1\n");
}
这篇关于POJ2010 Moo University - Financial Aid的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
