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

寝落ち。