제출 #1148133

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148133		ruben_ipenza	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	77 ms	12616 KiB

joi2019_ho_t4

import java.util.*;

class joi2019_ho_t4 {
    static class Node {
        int x, y, cost;
        Node(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }
    }

    public static int minMoves(int N, int[][] positions) {
        List<int[]> targets = new ArrayList<>();
        for (int x = 1; x <= N; x++) {
            for (int y = 1; y <= 2; y++) {
                targets.add(new int[]{x, y});
            }
        }

        boolean[] assigned = new boolean[2 * N];
        boolean[] targetAssigned = new boolean[2 * N];

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));
        int totalCost = 0;

        for (int i = 0; i < 2 * N; i++) {
            int minDist = Integer.MAX_VALUE, targetIdx = -1;
            for (int j = 0; j < 2 * N; j++) {
                if (targetAssigned[j]) continue;
                int dist = Math.abs(positions[i][0] - targets.get(j)[0]) + Math.abs(positions[i][1] - targets.get(j)[1]);
                if (dist < minDist) {
                    minDist = dist;
                    targetIdx = j;
                }
            }
            totalCost += minDist;
            targetAssigned[targetIdx] = true;
        }

        return totalCost;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] positions = new int[2 * N][2];
        for (int i = 0; i < 2 * N; i++) {
            positions[i][0] = sc.nextInt();
            positions[i][1] = sc.nextInt();
        }
        System.out.println(minMoves(N, positions));
        sc.close();
    }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63