POJ 2010 Moo University – Financial Aid
奶牛大学:奶大招生,从C头奶牛中招收N头。它们分别得分score_i,需要资助学费aid_i。希望新生所需资助不超过F,同时得分中位数最高。求此中位数。
3.1不光是查找值!“二分搜索”
最小化第k大的值
在2.4节的时候用最大堆做过这道题,现在用二分再做一遍。在分别排序分数和学费之后,以分数为界限将牛分为左右两个区间,统计左区间符合条件的数目left和右区间的数目right。讨论left 和right是否满足条件。以此为基础二分,实际上下面的谓词逻辑可以优化,但是目前看起来比较好懂。
#include <iostream> #include <algorithm> using namespace std; #define MAX_COW 100000 + 16 int N, C, F; int lower[MAX_COW], upper[MAX_COW]; struct Cow { int rank_by_score, score, aid; }; Cow cow_score[MAX_COW], cow_aid[MAX_COW]; bool less_by_score(Cow& a, Cow& b) { return a.score < b.score; } bool less_by_aid(Cow& a, Cow& b) { return a.aid < b.aid; } ///////////////////////////SubMain////////////////////////////////// int main(int argc, char *argv[]) { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif ios::sync_with_stdio(false); cin.tie(0); cin >> N >> C >> F; int half = N / 2; for (int i = 0; i < C; ++i) { cin >> cow_score[i].score >> cow_score[i].aid; // 分数 学费 } sort(cow_score, cow_score + C, less_by_score); for (int i = 0; i < C; ++i) { cow_score[i].rank_by_score = i; } memcpy(cow_aid, cow_score, sizeof(Cow) * C); sort(cow_aid, cow_aid + C, less_by_aid); int lb = 0, ub = C, ans = -1; while (ub - lb > 1) { int mid = (ub + lb) >> 1; // 将牛分为左右两个区间,统计左区间符合条件的数目left和右区间的数目right // 情况比较多,总体是二分,实际上有四种情况 int left = 0, right = 0, total_aid = cow_score[mid].aid; for (int i = 0; i < C; ++i) { if ((cow_aid[i].rank_by_score < mid) && (total_aid + cow_aid[i].aid <= F) && (left < N / 2)) { total_aid += cow_aid[i].aid; ++left; } else 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 < N / 2) && (right < N / 2)) { ans = -1; break; } else if (left < N / 2) { lb = mid; } else if (right < N / 2) { ub = mid; } else { ans = cow_score[mid].score; lb = mid; } } cout << ans << endl; #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt"); #endif return 0; } ///////////////////////////End Sub//////////////////////////////////
12848172 | hankcs | 2010 | Accepted | 2580K | 797MS | C++ | 1982B | 2014-05-07 12:08:57 |