SRM476 Div1 Easy Badgers
問題
あなたは何匹か動物(Badger)を飼おうとしている。 候補の動物は $n$ 匹いて。$i$ 匹目の動物は、それ一匹だけだと一日の食事で $hunger[i]$ 個の餌を食べる。 また、その他にその他の $k$ 匹飼っていると、加えて $greed[i] \times k$ 個の餌を食べる。
あなたが一度の食事に用意できる餌の量の合計の上限 ($totalFood$) が決まっている。 飼うことが出来る動物の数の最大値を求めなさい。
方針
$k$ 匹目の動物を飼うとすると、$i$ 番目の動物が消費する量は $ hunger[i] + greed[i] \times (k-1) $ です。 これを全ての動物で求め、昇順にソートして前から $k$ 匹を選べば 餌の消費量を最小化できます。
$k$ を $n$ から $0$ まで順に試し、可能だと判断された所でその値を返します。 二分探索しなくても間に合います。
実装
class Badgers {
public:
vi a,b;
int lim;
int n;
int feedMost( vector <int> a_, vector <int> b_, int lim_ ) {
tie(a,b,lim) = tie(a_,b_,lim_);
n = a.size();
for(int i=n;i>=0;i--) if(check(i)) return i;
return -1;
}
bool check(int k){
vi v(n);
rep(i,n) v[i] = a[i] + (k-1)*b[i];
int s = 0;
sort(all(v));
rep(i,k) s += v[i];
return s <= lim;
}
};