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; }