Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-08-05SRM300台を練習していく part7

SRM 310 FloatingMedian

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

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

ソート済みのlistに対してはCollections.binarySearchが使えるので、

インデックスをずらす際に取り除く値の位置と、新しくリストに挿入する値の位置を二分探索で探してあげる。


import java.util.ArrayList;
import java.util.List;

public class FloatingMedian {

	public long sumOfMedians(int seed, int mul, int add, int N, int K) {
		long[] nums = new long[N];
		nums[0] = seed;
		for (int i = 1 ; i < N ; i++) {
			nums[i] = ((1L * nums[i-1] * mul + add) % 65536);
		}
		List<Long> ls = new ArrayList<Long>();
		for (int i = 0 ; i < K ; i ++) {
			ls.add(nums[i]);
		}
		java.util.Collections.sort(ls);

		long med = ls.get((K+1)/2-1);
		
		for (int i = 0 ; i < N - K ; i++) {
			int rem = java.util.Collections.binarySearch(ls, nums[i]);
			ls.remove(rem);
			int ins = java.util.Collections.binarySearch(ls, nums[i+K]);
			if (ins < 0) {
				ins = -ins - 1;
			}
			ls.add(ins, nums[i+K]);
			med += ls.get((K+1)/2-1);
		}

		return med;
	}

}