放牧代码和思想
专注自然语言处理、机器学习算法

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

POJ 2010 Moo University – Financial Aid

奶牛大学:奶大招生,从C头奶牛中招收N头。它们分别得分score_i,需要资助学费aid_i。希望新生所需资助不超过F,同时得分中位数最高。求此中位数。

最大堆

2.4 加工并储存数据的数据结构

优先队列

先将奶牛排序,考虑每个奶牛作为中位数时,比它分数低(前面的)的那群牛的学费总和lower_i,后面的总和upper_i。然后从分数高往分数低扫描,满足aid_i + lower_i + upper_i <= F的第一个解就是最优解。

相比于这种“枚举”,还有一种利用二分搜索的快速实现:http://www.hankcs.com/program/cpp/poj-2010-moo-university-financial-aid-binary-search.html

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <algorithm>
#include <queue>
#include <limits>
#include <functional>
using namespace std;

#define MAX_COW 100000 + 16

int N, C, F;
pair<int, int> cow[MAX_COW];
// 牛i作为中位数时,lower[i]表示分数低于它的牛的学费总和
int lower[MAX_COW], upper[MAX_COW];

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	cin >> N >> C >> F;
	int half = N / 2;
	for (int i = 0; i < C; ++i)
	{
		cin >> cow[i].first >> cow[i].second;	// 分数 <-> 学费
	}
	sort(cow, cow + C);
	{
		int total = 0;
		priority_queue<int> q;
		for (int i = 0; i < C; ++i)
		{
			lower[i] = q.size() == half ? total : 0x3f3f3f3f;
			q.push(cow[i].second);
			total += cow[i].second;
			if (q.size() > half)
			{
				// 然后踢掉一个学费最高的家伙
				total -= q.top(); q.pop();
			}
		}
	}

	{
		int total = 0;
		priority_queue<int> q;
		for (int i = C - 1; i >= 0; --i)
		{
			upper[i] = q.size() == half ? total : 0x3f3f3f3f;
			q.push(cow[i].second);
			total += cow[i].second;
			if (q.size() > half)
			{
				// 然后踢掉一个学费最高的家伙
				total -= q.top(); q.pop();
			}
		}
	}

	int result;
	for (int i = C - 1; i >= 0; --i)
	{
		if (lower[i] + cow[i].second + upper[i] <= F)
		{
			result = cow[i].first;
			break;
		}
	}

	cout << result << endl;
	
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 2010 Moo University – Financial Aid 题解 《挑战程序设计竞赛》

分享到:更多 ()

评论 4

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #4

    3 5 17
    1 2
    7 2
    8 16
    9 13
    11 15

    huchi2个月前 (08-13)回复
  2. #3

    还有, 给个小建议 你的代码常数太大, 也可能是cin和cout的缘故. 抄了你的代码但是比你快四倍, 我们汉子就应该追求速度是不?

    Likecer2年前 (2015-08-11)回复
  3. #2

    你的题目翻译都萌哒哒的, 一定是男孩子…

    Likecer2年前 (2015-08-10)回复
  4. #1

    赞!

    Jecvay3年前 (2014-07-25)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机