AOJ 1295: Cubist Artwork

問題: Cubist Artwork | Aizu Online Judge

ブロックを積み上げて作った立体について、上の図のように横から見た図と正面から見た図が与えられるので、それらを満たす立体を作るのに必要な最小のブロックの数を答える。

解法: 上の例では、下の図の赤字のようにブロックを配置することで、横から見た時のの3と4を、正面から見た時の3と4とそれぞれペアにして満たせる。

残った横の1と正面の2と3はペアにして満たす方法がないので、個別に満たせるようにブロックを置く必要がある。処理としては、横から見えるブロックのリストと正面から見えるブロックのリストをそれぞれソートして、同じ数字同士でペアを作っていき、残った数字を個別に足せば良い。

解答コード:

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            int frontNum = scanner.nextInt();
            int sideNum = scanner.nextInt();
            if (frontNum == 0) {
                scanner.close();
                break;
            }

            // 優先度つきキュー（小さい方から出てくる）
            PriorityQueue<Integer> front = new PriorityQueue<Integer>();
            PriorityQueue<Integer> side = new PriorityQueue<Integer>();

            for (int i = 0; i < frontNum; i++) {
                front.add(scanner.nextInt());
            }

            for (int i = 0; i < sideNum; i++) {
                side.add(scanner.nextInt());
            }

            int ans = 0;
            while (!front.isEmpty() || !side.isEmpty()) {
                if (front.peek() == side.peek()) {
                    /* 両方のキューの先頭が一緒なら両方出す （ペアを作る） */
                    ans += front.poll();
                    side.poll();
                } else if (side.isEmpty()
                        || (!front.isEmpty() && front.peek() < side.peek())) {
                    // どちらかが空か、ペアにならない数字が残っていたらそれを出す
                    ans += front.poll();
                } else if (front.isEmpty() || front.peek() > side.peek()) {
                    ans += side.poll();
                }
            }

            System.out.println(ans);
        }

    }
}