分析：如果用二分法，关键是score和aid分开排序，score排序是为了充分利用中位数的性质，这样就可以确定m左右必须各选N/2个，到这之后有人是用dp求最优解，可以再次按照aid排序一次，可以直接确定最优解（肯定是从最小的开始选择！）：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int N, C, F;
const int maxn = ;
struct Cow{
int id, score, aid;
}Score[maxn], Aid[maxn];
bool cmp_score( const Cow &a, const Cow &b) {
return a.score < b.score;
}
bool cmp_aid(const Cow &a, const Cow &b) {
return a.aid < b.aid;
}
int main(void) { scanf("%d%d%d", &N, &C, &F);
for (int i = ; i < C; i++) scanf("%d%d", &Score[i].score, &Score[i].aid);
sort(Score, Score+C, cmp_score);
for (int i = ; i < C; i++) Score[i].id = i;
memcpy(Aid, Score, sizeof(Cow)*C);
sort(Aid, Aid+C, cmp_aid);
int l = , u = C, ans = -;
while (u-l > ) {
int m = (u+l) >> ;
int left = , right = , total = Score[m].aid;
for (int i = ; i < C; i++) {
if (Aid[i].id < m && (total+Aid[i].aid) <= F && left < N/) {
total += Aid[i].aid;
left++;
} else if (Aid[i].id > m && (total+Aid[i].aid) <= F && right < N/) {
total += Aid[i].aid;
right++;
}
}
if (left < N/ && right < N/) {//insufficient
ans = -;
break;
} else if (left < N / ) {
l = m;
} else if (right < N / ){
u = m;
} else {
ans = Score[m].score;
l = m;
}
}
printf("%d\n", ans);
return ;
}
百度还看到用堆、优先队列做的！mark。
参考：
《挑战程序设计竞赛》3.1