Codeforces Round #310 Div1 B: Case of Fugitive

問題

codeforces.com

解法

島とに対して架けられる橋の長さaは

を満たさなければならない。

, とおいて、shortDでソートしておく。

ある距離lengthについて小さい方から見ていく。shortD=lengthとなる島間距離があったら取り出して、longDを優先度つきキューに入れておく。こうすることで残った島間距離は必ずlength以上になる。
次に、長さlengthの橋を、キューに入った距離に順番に当てはめていく。こうすることでキューに入った距離longDは全てlength以下になる。

ほぼ同じ問題:kenkoooo.hatenablog.com

コード

import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	public void solve() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long M = sc.nextLong();
		long[][] islands = new long[N][2];
		for (int i = 0; i < N; i++) {
			islands[i][0] = sc.nextLong();
			islands[i][1] = sc.nextLong();
		}

		PriorityQueue<Distance> shortQueue = new PriorityQueue<>();
		long[] longDist = new long[N - 1];
		for (int i = 0; i < N - 1; i++) {
			long s = islands[i + 1][0] - islands[i][1];
			longDist[i] = islands[i + 1][1] - islands[i][0];
			shortQueue.add(new Distance(i, s));
		}

		PriorityQueue<Distance> longQueue = new PriorityQueue<>();
		PriorityQueue<Distance> bridgeQueue = new PriorityQueue<>();
		for (int i = 0; i < M; i++) {
			bridgeQueue.add(new Distance(i, sc.nextLong()));
		}
		sc.close();

		ArrayList<Distance> ans = new ArrayList<>();
		while (true) {
			long length = bridgeQueue.peek().length;
			if (!shortQueue.isEmpty() && shortQueue.peek().length < length) {
				length = shortQueue.peek().length;
			}

			while (!shortQueue.isEmpty() && shortQueue.peek().length == length) {
				Distance shortDist = shortQueue.poll();
				longQueue.add(new Distance(shortDist.id, longDist[shortDist.id]));
			}

			while (!bridgeQueue.isEmpty() && bridgeQueue.peek().length == length) {
				Distance bridge = bridgeQueue.poll();
				while (!longQueue.isEmpty() && longQueue.peek().length < length) {
					longQueue.poll();
				}
				if (!longQueue.isEmpty()) {
					ans.add(new Distance(bridge.id, longQueue.poll().id));
				}
			}
			if (bridgeQueue.isEmpty()) {
				break;
			}
		}

		Collections.sort(ans);
		if (ans.size() != N - 1) {
			System.out.println("No");
		} else {
			System.out.println("Yes");
			StringBuilder sb = new StringBuilder();
			for (Distance bridge : ans) {
				sb.append((bridge.id + 1) + " ");
			}
			System.out.println(sb.toString().trim());
		}
	}

	public static void main(String[] args) {
		new Main().solve();
	}

}

class Distance implements Comparable<Distance> {
	long length;
	int id;

	public Distance(int id, long length) {
		this.length = length;
		this.id = id;
	}

	@Override
	public int compareTo(Distance o) {
		return Long.signum(this.length - o.length);
	}
}