SRM476 Div1 Easy(250), Div2 Medium(500) Badgers

TopCoder

Badgers

n匹のアナグマを飼えるかどうかを、0≦n≦Nについて調べる。飼うアナグマは餌の少ないものを貪欲に選ぶ。

#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

class Badgers
{
public:
    int feedMost( vector <int> hunger, vector <int> greed, int totalFood );
};

int Badgers::feedMost( vector <int> hunger, vector <int> greed, int totalFood )
{
    int N = (int)hunger.size();

    for ( int n=N; n>0; n-- )
    {
        vector<int> f;
        for ( int i=0; i<N; i++ )
            f.push_back( hunger[i] + greed[i]*(n-1) );

        sort( f.begin(), f.end() );

        if ( accumulate( f.begin(), f.begin()+n, 0 ) <= totalFood )
            return n;
    }

    return 0;
}