SRM476
250を解いて550を考えていたら、いつの間にか朝でした。
寝落ちは初体験。
250 Badgers
barger数をKに固定したときに、hunger+greed*(K-1)が小さい順にbargerをK個選択すれば、bargerがK個の時に必要な最小食料が導出されます。この最小食料をtotalFoodと比較するだけ。
class Badgers { public: int feedMost(vector<int> hunger, vector<int> greed, int totalFood) { vector<int> test; for(int i=1; i<=(int)hunger.size(); i++){ for(int j=0; j<(int)hunger.size(); j++){ test.push_back(hunger[j] + greed[j] * (i-1)); } sort(test.begin(),test.end()); int reqF = 0; for(int j=0; j<i; j++){ reqF += test[j]; } if(reqF > totalFood){ return i-1; } test.clear(); } return hunger.size(); } };
550 FriendTour
寝落ち。