SRM 499 Div2 500 -> 411

2011-03-08

03:08 |

ヒントの数字 a, b が異なる場合、a+1 匹の色と b+1 匹の色は異なるので無条件に加算できる。
ヒントの数字 a, b が同じ場合、最大 a+1 匹が a と答えられる。ので、同じ数字は a+1 個まで１つにまとめられる。
以上、map に登録しながらうさぎの数を数える。

class ColorfulRabbits {
	public:
	int getMinimum(vector <int> re) {
		map<int, int> m;
		REP(i, re.SZ)
		{
			if(m.find(re[i]+1) == m.end()) m[re[i]+1] = 0;
			m[re[i]+1]++;
		}
		int ans = 0;
		for( map<int, int>::const_iterator p = m.begin(); p!=m.end(); p++ )
		{
			//cout << p->first << ": " << p->second << " " << endl;
			ans += (p->second + p->first - 1) / p->first * p->first;
		}
		return ans;
	}