SRM 647 Easy: BuildingTowersEasy

コード

import java.util.PriorityQueue;

public class BuildingTowersEasy {

	public int maxHeight(int N, int[] x, int[] t) {
		for (int i = 0; i < x.length; i++) {
			for (int j = 0; j < x.length; j++) {
				t[i] = Math.min(t[i], t[j] + Math.abs(x[i] - x[j]));
				t[j] = Math.min(t[j], t[i] + Math.abs(x[i] - x[j]));
			}
		}

		PriorityQueue<Restriction> restrictions = new PriorityQueue<>();
		for (int i = 0; i < x.length; i++) {
			if (x[i] == 1) {
				continue;
			}
			restrictions.add(new Restriction(x[i] - 1, t[i]));
		}

		int max = 0;
		int[] height = new int[N];
		for (int i = 1; i < N; i++) {
			height[i] = height[i - 1] + 1;
			if (!restrictions.isEmpty()) {
				int id = restrictions.peek().id;
				if (id == i) {
					height[i] = Math.min(height[i], restrictions.poll().height);
				} else {
					height[i] = Math.min(height[i], restrictions.peek().height + (id - i));
				}
			}

			max = Math.max(max, height[i]);
		}

		return max;
	}

	static class Restriction implements Comparable<Restriction> {
		int id, height;

		public Restriction(int id, int h) {
			this.id = id;
			this.height = h;

		}

		@Override
		public int compareTo(Restriction o) {
			return this.id - o.id;
		}
	}

}