제출 #1148106

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148106		ferchostudio	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	104 ms	12712 KiB

joi2019_ho_t4

import java.util.*;

public class joi2019_ho_t4 {
  static class Position {
    int x, y;

    Position(int x, int y) {
      this.x = x;
      this.y = y;
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) return true;
      if (!(o instanceof Position)) return false;
      Position p = (Position) o;
      return x == p.x && y == p.y;
    }

    @Override
    public int hashCode() {
      return Objects.hash(x, y);
    }
  }

  public static int minMovesToTarget(int N, int[][] coins) {
    // Pre-calcular todos los objetivos posibles
    Position[] targets = new Position[2 * N];
    int idx = 0;
    for (int x = 1; x <= N; x++) {
      targets[idx++] = new Position(x, 1);
      targets[idx++] = new Position(x, 2);
    }

    // Convertir monedas a Position para consistencia
    Position[] coinPositions = new Position[2 * N];
    for (int i = 0; i < 2 * N; i++) {
      coinPositions[i] = new Position(coins[i][0], coins[i][1]);
    }

    // Pre-calcular todas las distancias Manhattan
    int[][] distances = new int[2 * N][2 * N];
    for (int i = 0; i < 2 * N; i++) {
      for (int j = 0; j < 2 * N; j++) {
        distances[i][j] = Math.abs(coinPositions[i].x - targets[j].x) +
            Math.abs(coinPositions[i].y - targets[j].y);
      }
    }

    // Usar un array para seguir los objetivos utilizados
    boolean[] usedTarget = new boolean[2 * N];
    int totalMoves = 0;

    // Para cada moneda, encontrar el objetivo más cercano disponible
    for (int i = 0; i < 2 * N; i++) {
      int minDist = Integer.MAX_VALUE;
      int bestTarget = -1;

      for (int j = 0; j < 2 * N; j++) {
        if (!usedTarget[j] && distances[i][j] < minDist) {
          minDist = distances[i][j];
          bestTarget = j;
        }
      }

      if (bestTarget != -1) {
        usedTarget[bestTarget] = true;
        totalMoves += minDist;
      }
    }

    return totalMoves;
  }

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    int[][] coins = new int[2 * N][2];

    for (int i = 0; i < 2 * N; i++) {
      coins[i][0] = scanner.nextInt();
      coins[i][1] = scanner.nextInt();
    }

    System.out.println(minMovesToTarget(N, coins));
    scanner.close();
  }
}

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