题意: 奶牛大学:奶大招生,从C头奶牛中招收N头。它们分别得分score_i,需要资助学费aid_i。希望新生所需资助不超过F,同时得分中位数最高。求此中位数。
解题思路:这里要求最大中位数,中位数肯定是在这些人中间,故可以枚举中位数,可以先对分数进行排序,然后用二分去找最大中位数。
每次枚举的中位数应该要检验是否满足题意:
这里有一个check函数,它的返回值含义如下:
-1 直接输出,不可能满足条件了
0 这种方案是满足条件的,可以把中位数调大试试
1 这种方案是不满足的,但是把中位数调大就有可能满足了(否则不可能满足)
2 这种方案是不满足的,但是把中位数调小就有可能满足了(否则不可能满足)