Topcoder SRM 499 div1 easy "ColorfulRabbits"
問題:http://www.topcoder.com/stat?c=problem_statement&pm=11327(要ログイン)
いくつかの数値が与えられる.この数値は,存在するうさぎのうちの誰かに自分と同じ色が何匹いるかを尋ねた結果である.この数値群から得られるうさぎの総数を求める.
同じ数を答えるうさぎは同じ色である可能性があるため,そのうさぎたちをその数値+1(自分自身)でグループにする.あとはグループに属するうさぎの数とグループ数の積を合計する.
コード
import java.util.*; public class ColorfulRabbits { public int getMinimum(int[] replies) { Arrays.sort(replies); Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < replies.length; ++i) { Integer c = map.get(replies[i] + 1); if (c == null) { c = 0; } map.put(replies[i] + 1, c + 1); } int r = 0; for (Map.Entry<Integer, Integer> e : map.entrySet()) { int k = e.getKey(), v = e.getValue(); r += k * (v / k + (v % k > 0 ? 1 : 0)); } return r; } }