kmjp's blog

競技プログラミング参加記です

TopCoder SRM 570 Div2 Easy Chopsticks

さてDiv2も練習。
http://community.topcoder.com/stat?c=problem_statement&pm=12424

問題

色んな長さの箸が1本ずつある。
同じ長さの箸が2本あると1組の箸となる。
箸の長さが配列で与えられたとき、作れる箸の組数を答える。

解法

長さ別に数を数え、2で割ったものが作れる箸の数。

class Chopsticks {
	int num[101];
	public:
	int getmax(vector <int> length) {
		int i,n=0;
		ZERO(num);
		FOR(i,length.size()) num[length[i]]++;
		FOR(i,101) n += num[i]/2;
		return n;
	}
};

まとめ

Div2 Easyとはいえ妙に簡単な問題だね。

広告を非表示にする