Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-03-27SRM300台を練習していく part2

SRM 305 UnfairDivision

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

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

各人のassetsの分け方の全パターンを列挙する。


public class UnfairDivision {

	public int albertsShare(int[] assets) {
		int len = assets.length;
		int max_al = 0;
		for (int i = 1 ; i < len ; i++) {
			int al = 9999999;
			int bet = 0;
			for (int j = 1 ; j < len ; j++) {
				if (i == j) {
					continue;
				}
				int a = Math.min(i, j);
				int b = Math.max(i, j);
				int sa = 0, sb = 0, sc = 0;
				for (int x = 0 ; x < a ; x++) {
					sa += assets[x];
				}
				for (int x = a ; x < b ; x++) {
					sb += assets[x];
				}
				for (int x = b ; x < len ; x++) {
					sc += assets[x];
				}
				int max = Math.max(sa, Math.max(sb, sc));
				int min = Math.min(sa, Math.min(sb, sc));
				int mid = sa + sb + sc - max - min;
				if (bet < mid) {
					al = min;
					bet = mid;
				} else if (bet == mid){
					al = Math.min(al, min);
				}
			}
			if (max_al < al) {
				max_al = al;
			}
		}
		return max_al;
	}

}