TopCoder SRM 562 Div2 Easy CucumberMarket

今回は不参加だったけど、最終的にunratedだったのね。
まずは手始めにdiv2 easy。
http://community.topcoder.com/stat?c=problem_statement&pm=12319

N個の商品のうちM個を選んだ時、合計価格がKを超えるか判定する問題。
高い順にM個選んだ場合にKを超えるか判定するだけなので簡単。

class CucumberMarket {
	public:
	string check(vector <int> price, int budget, int k) {
		int i,t;
		sort(price.begin(),price.end(),greater<int>());
		t=0;
		FOR(i,k) t+=price[i];
		
		return (t>budget)?string("NO"):string("YES");
	}
};

まとめ

最初「n_C_m個のパターンを全部試さないといけない？、Div2 Easyでそんなん出る？」と迷ってしまったが、考えてみたら非常に楽だった。
今まで、降順ソートはsort後reverseしてたけど、greater使えばsortだけで行けるのね。