POJ-2010 : Moo University - Financial Aid

問題概要

重さw[i]、価値v[i]の商品がC(<10^5)個ある。この中からN(:odd)個の商品を選び、重さの和がF(<10^9)以下で価値の中央値が最大になるようにしたい。最大値を求める問題、無理なら指摘する。

解法

どの商品が中央値にくるかを全探索する。その商品以下の価値からN/2個、それ以上からN/2個選ぶときは重さの小さいものを貪欲に選べばよいので、これはheapを使えば前処理で効率的に計算しておくことができる。

acceptされたコード

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

typedef long long int64;

const int MAX_C = (int)(1e5);
const int64 INF = 1LL<<60;

int N, C;
int64 F;
struct cow{
	int score, cost;
};

bool operator<(const cow& lhs,  const cow& rhs){
	return lhs.score < rhs.score;
}

cow cs[MAX_C];
int64 lower[MAX_C], upper[MAX_C];

void init(){
	scanf("%d%d%lld", &N, &C, &F);
	for(int i=0; i<C; ++i){
		scanf("%d%d", &cs[i].score, &cs[i].cost);
	}
}

int solve(){
	sort(cs, cs+C);
	const int half = N / 2;

	//lower
	{
		priority_queue< int64 > que;
		int64 acc = 0;
		for(int i=0; i<C; ++i){
			lower[i] = (int)que.size() == half ? acc : INF;
			acc += cs[i].cost;
			que.push(cs[i].cost);
			if((int)que.size() > half){
				acc -= que.top();
				que.pop();
			}
		}
	}

	//upper
	{
		priority_queue< int64 > que;
		int64 acc = 0;
		for(int i=C-1; i>=0; --i){
			upper[i] = (int)que.size() == half ? acc : INF;
			acc += cs[i].cost;
			que.push(cs[i].cost);
			if((int)que.size() > half){
				acc -= que.top();
				que.pop();
			}
		}
	}

	for(int i=C-1; i>=0; --i){
		if(cs[i].cost +  lower[i] + upper[i] <= F){
			return cs[i].score;
		}
	}

	return -1;
}

int main(){
	init();
	printf("%d\n", solve());

	return 0;
}