제출 #1148147

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

class joi2019_ho_t4 {

    public static int minStepsRecur(int[] coinsX, int[] coinsY, int[] targetX, int[] targetY, int l, int r) {
        if (l >= r) return 0;

        int m = l;
        for (int i = l; i < r; i++) {
            if (coinsX[i] < coinsX[m]) {
                m = i;
            }
        }
        return Math.min(r - l,
                minStepsRecur(coinsX, coinsY, targetX, targetY, l, m) +
                        minStepsRecur(coinsX, coinsY, targetX, targetY, m + 1, r) +
                        Math.abs(coinsX[m] - targetX[m]) + Math.abs(coinsY[m] - targetY[m]));
    }

    public static int minSteps(int[] coinsX, int[] coinsY, int N) {
        int[] targetX = new int[N];
        int[] targetY = new int[2 * N];

        // Generamos las posiciones de destino de las monedas
        for (int i = 0; i < N; i++) {
            targetX[i] = i + 1;  // Las posiciones en X son 1..N
            targetY[i] = 1;      // La primera columna de destino
            targetY[N + i] = 2;  // La segunda columna de destino
        }

        return minStepsRecur(coinsX, coinsY, targetX, targetY, 0, N);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        int[] coinsX = new int[2 * N];
        int[] coinsY = new int[2 * N];

        for (int i = 0; i < 2 * N; i++) {
            coinsX[i] = sc.nextInt();
            coinsY[i] = sc.nextInt();
        }

        System.out.println(minSteps(coinsX, coinsY, N));
        sc.close();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...