POJ 2010 Moo University – Financial Aid 题解 《挑战程序设计竞赛》

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//////////////////////////////////