POJ2010 Moo University - Financial Aid(二分法)

题目地址

分析：如果用二分法，关键是score和aid分开排序，score排序是为了充分利用中位数的性质，这样就可以确定m左右必须各选N/2个，到这之后有人是用dp求最优解，可以再次按照aid排序一次，可以直接确定最优解（肯定是从最小的开始选择！）：

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 using namespace std;
 5 int N, C, F;
 6 const int maxn = 100010;
 7 struct Cow{
 8     int id, score, aid;
 9 }Score[maxn], Aid[maxn];
10 bool cmp_score( const Cow &a, const Cow &b) {
11     return a.score < b.score;
12 }
13 bool cmp_aid(const Cow &a, const Cow &b) {
14     return a.aid < b.aid;
15 }
16 int main(void) {
17
18     scanf("%d%d%d", &N, &C, &F);
19     for (int i = 0; i < C; i++) scanf("%d%d", &Score[i].score, &Score[i].aid);
20     sort(Score, Score+C, cmp_score);
21     for (int i = 0; i < C; i++) Score[i].id = i;
22     memcpy(Aid, Score, sizeof(Cow)*C);
23     sort(Aid, Aid+C, cmp_aid);
24     int l = 0, u = C, ans = -1;
25     while (u-l > 1) {
26         int m = (u+l) >> 1;
27         int left = 0, right = 0, total = Score[m].aid;
28         for (int i = 0; i < C; i++) {
29             if (Aid[i].id < m && (total+Aid[i].aid) <= F && left < N/2) {
30                 total += Aid[i].aid;
31                 left++;
32             } else if (Aid[i].id > m && (total+Aid[i].aid) <= F && right < N/2) {
33                 total += Aid[i].aid;
34                 right++;
35             }
36         }
37         if (left < N/2 && right < N/2) {//insufficient
38             ans = -1;
39             break;
40         } else if (left < N / 2) {
41                 l = m;
42         } else if (right < N / 2){
43                 u = m;
44         } else {
45             ans = Score[m].score;
46             l = m;
47         }
48     }
49     printf("%d\n", ans);
50     return 0;
51 }

View Code

百度还看到用堆、优先队列做的！mark。

参考：

《挑战程序设计竞赛》3.1