제출 #1148110

#제출 시각아이디문제언어결과실행 시간메모리
1148110ferchostudioCoin Collecting (JOI19_ho_t4)Java
0 / 100
78 ms12868 KiB
import java.util.*;

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

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

  private static long calculateDistance(Position from, Position to) {
    return Math.abs(from.x - to.x) + Math.abs(from.y - to.y);
  }

  public static long minMovesToTarget(int N, long[][] coins) {
    Position[] coinPositions = new Position[2 * N];
    Position[] targets = new Position[2 * N];

    // Crear posiciones de monedas
    for (int i = 0; i < 2 * N; i++) {
      coinPositions[i] = new Position(coins[i][0], coins[i][1]);
    }

    // Crear posiciones objetivo
    int idx = 0;
    for (int x = 1; x <= N; x++) {
      targets[idx++] = new Position(x, 1);
      targets[idx++] = new Position(x, 2);
    }

    boolean[] usedTarget = new boolean[2 * N];
    long totalMoves = 0;

    // Para cada moneda
    for (int i = 0; i < 2 * N; i++) {
      long minDist = Long.MAX_VALUE;
      int bestTarget = -1;

      // Encontrar el objetivo más cercano no usado
      for (int j = 0; j < 2 * N; j++) {
        if (!usedTarget[j]) {
          long dist = calculateDistance(coinPositions[i], targets[j]);
          if (dist < minDist) {
            minDist = dist;
            bestTarget = j;
          }
        }
      }

      usedTarget[bestTarget] = true;
      totalMoves += minDist;
    }

    return totalMoves;
  }

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

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

    System.out.println(minMovesToTarget(N, coins));
    scanner.close();
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...