本文共 2005 字，大约阅读时间需要 6 分钟。
题意：
一共C个学生，学校要录N(奇数)个，每个学生的分数和需要的aid给出，学校最多能提供F资金，求录取的学生中分数中位数最大。
题解：
方法1：对所有的学生按照分数进行从小到大排序，左边从第N/2+1个学生开始，到第C-N/2个学生结束，算出每个学生以他的分数为中位数，左边需要的最小总aid，需要用到优先队列！
同样地，对右边也进行计算，以每个学生自身为中位数，右边需要的最小总aid。
最后从右往左扫描，算出以每个学生为中位数，左右需要的总aid，<=F即可！
方法2：二分。对于每个mid看是否满足左右两边的score=N/2，并且aid<=F。
#include #include #include #include #include #include using namespace std; struct node { int score,aid,left,right; };bool cmp(struct node x1,struct node x2){ return x1.score >N>>C>>F; for(int i=1; i<=C; i++) scanf("%d%d",&a[i].score,&a[i].aid); sort(a+1,a+C+1,cmp); priority_queue q; int sum=0; if(N>1) { //前N/2个肯定不能当中位数 for(int i=1; i<=N/2; i++) { q.push(a[i].aid); sum+=a[i].aid; } //从N/2+1开始，计算分数比他小的N/2个最少需要多少aid for(int i=N/2+1; i<=C-N/2; i++) { a[i].left=sum; if(a[i].aid C-N/2; i--) { q.push(a[i].aid); sum+=a[i].aid; } for(int i=C-N/2; i>=N/2+1; i--) { a[i].right=sum; if(a[i].aid N/2; i--) { int total=a[i].left+a[i].right+a[i].aid; if(total<=F) { ans=a[i].score; break; } } cout< <
#include #include #include #include #include #include using namespace std;const int maxn=100000+5;struct node{int rank_by_score,score,aid;};node cow_score[maxn],cow_aid[maxn];bool less_by_score(struct node a,struct node b){ return a.score >N>>C>>F; for(int i=1;i<=C;i++) scanf("%d%d",&cow_score[i].score,&cow_score[i].aid); sort(cow_score+1,cow_score+1+C,less_by_score); for(int i=1;i<=C;i++) cow_score[i].rank_by_score=i; memcpy(cow_aid,cow_score,sizeof(node)*(C+1)); sort(cow_aid+1,cow_aid+C+1,less_by_aid); int lb=1,ub=C,ans=-1; while(ub-lb>1) { int mid=(lb+ub)>>1; int left=0,right=0,total_aid=cow_score[mid].aid; for(int i=1;i<=C;i++)//按照aid从小到大 扫描 { //每次去找mid 左右两边 aid总和最小的。如果能找到符合条件的，则left,right最后应该都为N/2； //如果扫描一遍 left,right 都小于N/2，那么就是没有符合题意的解了。 if(cow_aid[i].rank_by_score mid && total_aid+cow_aid[i].aid<=F && right< N/2 ) { total_aid+=cow_aid[i].aid; right++; } } if(left
转载地址：http://nyyci.baihongyu.com/