Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-10SRM380,SRM381,SRM382 (Practice)

SRM 380 CompilingDecksWithJokers

|  SRM 380 CompilingDecksWithJokers - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 380 CompilingDecksWithJokers - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8228

  • 圧倒的数学ゲー
    • いい問題
  • カードの残り数でソート
    • 一番小さな数 a が n個あって、その次に大きな数がb個あったら・・・
    • aとbが等しくなるには何枚ジョーカーを使う必要があるかで式を立ててゴニョゴニョ
  • n=1かつa=0のときに注意する
import java.util.Arrays;

public class CompilingDecksWithJokers {

	public int maxCompleteDecks(int[] cards, int jokers) {
		int len = cards.length;
		if (len == 1) {
			return cards[0] + jokers;
		}
		
		long cnt = 0;
		Arrays.sort(cards);
		while (jokers >= 1 && (cards[0] >= 1 || cards[1] >= 1)) {
			int samecnt = 0;
			long secondcnt = Integer.MAX_VALUE;
			for (int i = 0 ; i < len ; i++) {
				if (cards[i] == cards[0]) {
					samecnt++;
				}
			}
			if (samecnt < len) {
				secondcnt = cards[samecnt];
			}
			long willdo = Math.min(Math.min(secondcnt, jokers), (0L + secondcnt - cards[0]) * samecnt);
			if (samecnt >= 2) {
				willdo = Math.min(willdo, 1L * cards[0] * samecnt / (samecnt - 1));
			}
			long dec = 0, mod = 0;
			dec = willdo - willdo / samecnt;
			mod = willdo % samecnt;
			for (int i = 0 ; i < len ; i++) {
				if (i < samecnt) {
					cards[i] -= ((i < mod) ? (dec - 1) : dec);
				} else {
					cards[i] -= willdo;
				}
			}
			jokers -= willdo;
			cnt += willdo;
			Arrays.sort(cards);
		}
		Arrays.sort(cards);
		return (int) (cnt + cards[0]);
	}
}