問題
http://community.topcoder.com/stat?c=problem_statement&pm=10797&rd=14186
動物BadgersがN匹おり、できるだけ多く飼いたい。
ただし１日に与えられる餌がtotalFoodしかないため、この餌の中で
できるだけ多くの動物を飼うようにしたい。
各Badgersは一人でいるときに必要な餌の数hungerと、複数匹飼われたときに
追加で必要な餌greedが与えられる。
例えば４匹飼われた際はhunger+greed*3の餌が必要になる。
このとき、最大で何匹のBadgersが飼えるか求める。
解き方
Nは50のため、すべての組み合わせは確かめられない。
ここで、何匹買うかの情報を固定すると、そのときに必要な餌の量は
固定値となるため、貪欲法で求めることができる。
よって、飼う匹数を１〜Nまで固定して、
それぞれについて貪欲法で選んだ時にtotalFoodに収まる
最大の匹数を求めればよい。
コード
class Badgers {
public: int feedMost(vector<int> hunger, vector<int> greed, int totalFood) {
int n=hunger.size();
int ret=0;
for(int num=1;num<=n;num++){
vector<int> vx;
FORE(i,0,n){
int cost=hunger[i]+greed[i]*(num-1);
vx.push_back(cost);
}
sort(all(vx));
int sum=0;
FORE(i,0,num)sum+=vx[i];
if(totalFood>=sum)ret=max(ret,num);
}
return ret;
}
};
public: int feedMost(vector<int> hunger, vector<int> greed, int totalFood) {
int n=hunger.size();
int ret=0;
for(int num=1;num<=n;num++){
vector<int> vx;
FORE(i,0,n){
int cost=hunger[i]+greed[i]*(num-1);
vx.push_back(cost);
}
sort(all(vx));
int sum=0;
FORE(i,0,num)sum+=vx[i];
if(totalFood>=sum)ret=max(ret,num);
}
return ret;
}
};