首页 > 代码库 > POJ2010 Moo University - Financial Aid
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_JUDGE freopen("G:/1.txt","r",stdin); freopen("G:/2.txt","w",stdout); #endif int 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"); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。