Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-10SRM346 (Practice)

SRM 346 HeightRound

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

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

  • 貪欲法。難しい
    • editorialや他の人のコードを見ながら書いた。
    • 要復習
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class HeightRound {
	public int[] getBestRound(int[] h) {
		int len = h.length;
		Arrays.sort(h);
		int[] ret = new int[len];
		ret[0] = h[0];
		for (int d = 0 ; d <= 1000 ; d++) {
			boolean isok = true;
			List<Integer> hv = new ArrayList<Integer>();
			for (int i = 1 ; i < len ; i++) {
				hv.add(h[i]);
			}
			int q = h.length - 1;
			while (q > 0) {
				int idx = hv.size() - 1;
				int prev = (q + 1 == ret.length) ? ret[0] : ret[q+1];
				while (idx >= 0) {
					if (Math.abs(hv.get(idx) - prev) <= d) {
						break;
					}
					idx--;
				}
				if (idx < 0) {
					isok = false;
					break;
				}
				ret[q] = hv.remove(idx);
				q--;
			}
			if (Math.abs(ret[1] - ret[0]) > d) {
				continue;
			}
			if (isok) {
				return ret;
			}
		}
		return ret;
	}
}