SRM476 Div1 Easy Badgers

2015/04/17 (Fri) SRM 貪欲

問題

問題文

あなたは何匹か動物(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;
    }
};