GCJ2011 Round 1C B "Space Emergency"

問題：https://code.google.com/codejam/contest/dashboard?c=1128486#s=p1

星の間の距離が与えられる．すべての星を通って最後まで到着する時間を求める．ただし，ある時間以降はブースターを数個作られ，これを使うと各星の間の航行速度を二倍にすることができる．

星の距離は繰り返しになっているのでこれをすべて展開して持っておいて，ブースターができるまでの時間を足し，ブースターができてからは，かかる時間の大きい順に一個ずつ使って時間を足してゆく．

コード

import java.util.*;

public class B {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		for (int test = 1, Test = s.nextInt(); test <= Test; ++test) {
			int L = s.nextInt();
			long T = s.nextLong();
			int N = s.nextInt(), C = s.nextInt();
			int[] a = new int[C];
			for (int i = 0; i < C; ++i) {
				a[i] = s.nextInt();
			}
			Deque<Integer> q = new ArrayDeque<Integer>();
			for (int i = 0; i < N; ++i) {
				q.add(a[i % C] * 2);
			}

			long t = 0;

			for (; t < T && !q.isEmpty();) {
				int d = q.poll();
				if (t + d < T) {
					t += d;
				} else {
					q.add((int) (t + d - T));
					t = T;
				}
			}
			List<Integer> list = new ArrayList<Integer>(Arrays.asList(q
					.toArray(new Integer[0])));
			Collections.sort(list);
			for (int l = 1; l <= L && list.size() - l >= 0; ++l) {
				list.set(list.size() - l, list.get(list.size() - l) / 2);
			}
			
			for(long v : list){
				t += v;
			}

			System.out.println("Case #" + test + ": " + t);
		}
	}
	
}