题意大概说下
N头奶牛想上大学，每个奶牛有一个SAT分数和一个助学金数目。奶牛大学只能提供M个名额以及K助学金数目。求一种分配方案使得奶牛大学录取的牛中SAT分数在中位数上的分数最大。
思路:
可以对奶牛的分数排序后二分确定中位数。开两个数组,datas,datac，前者按照奶牛分数排序，后者按照奶牛助学金数目排序。二分枚举中位数，然后进行验证：
按照datac从低到高顺序在总和小于等于k的情况下统计处落在左区间的数目left和右区间的数目right
如果left>m/2&&right>m/2，当前方案可行，尝试中位数更大的方案
如果left<m/2&&right<m/2，则不可能
如果left<m/2&&right>m/2，中点应该向右移动
如果left>m/2&&right<m/2，中点应该向左移动
注意考虑中点的覆盖情况。
还有，可能调整到最后也没法满足条件，那么也输出-1
具体看程序吧
1 # include <cstdio>
2 using namespace std;
3 # include <algorithm>
4 # include <cstring>
5 int n,c,f;
6 struct node
7 {
8 int s,c;
9 int id;
10 }cows[100005],cowc[100005];
11 int rank[100005];
12 bool cmps(node a,node b)
13 {
14 return a.s<b.s;
15 }
16 bool cmpc(node a,node b)
17 {
18 return a.c<b.c;
19 }
20 int chk(int pos)
21 {
22 int left=0,right=0,tf=f;
23 bool mid=false;
24 for(int i=0;i<c;i++)
25 if(rank[cowc[i].id]<pos&&left<n/2)
26 if(tf>=cowc[i].c)
27 left++,tf-=cowc[i].c;
28 else break;
29 else if(rank[cowc[i].id]==pos&&!mid)
30 if(tf>=cowc[i].c)
31 mid=true,tf-=cowc[i].c;
32 else break;
33 else if(rank[cowc[i].id]>pos&&right<n/2)
34 if(tf>=cowc[i].c)
35 right++,tf-=cowc[i].c;
36 else break;
37 if(left>=n/2&&right>=n/2&&mid) return 0;
38 else if(left>=n/2) return 1;
39 else if(right>=n/2) return -1;
40 else if(left<n/2&&right<n/2) return -2;
41 }
42 int main()
43 {
44 scanf("%d%d%d",&n,&c,&f);
45 for(int i=0;i<c;i++)
46 {
47 scanf("%d%d",&cows[i].s,&cows[i].c);
48 cows[i].id=i;
49 }
50 memcpy(cowc,cows,sizeof(cows));
51 sort(cows,cows+c,cmps);
52 sort(cowc,cowc+c,cmpc);
53 /* printf("sorted by s\n");
54 for(int i=0;i<c;i++)
55 printf("(%d,%d)\n",cows[i].id,cows[i].s);
56 printf("\n");
57 printf("sorted by c\n");
58 for(int i=0;i<c;i++)
59 printf("(%d,%d)\n",cowc[i].id,cowc[i].c);
60 printf("\n");*/
61 int s=n/2,e=c-1-n/2;
62 for(int i=0;i<c;i++)
63 rank[cows[i].id]=i;
64 while(s<=e)
65 {
66 int mid=(s+e)/2;
67 switch(chk(mid))
68 {
69 case -1:
70 s=mid+1;
71 break;
72 case 1:
73 e=mid-1;
74 break;
75 case 0:
76 s=mid+1;
77 break;
78 case -2:
79 printf("-1\n");
80 return 0;
81 };
82 }
83 if(chk(s-1)==0)
84 printf("%d\n",cows[s-1].s);
85 else
86 printf("-1\n");
87 // system("pause");
88 return 0;
89 }
90