Untitled
unknown
plain_text
a year ago
1.4 kB
3
Indexable
class S { static int[] R; static int Ans = 0; static int N, M, K; public static void main(String args[]) throws Exception { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int tc = 1; tc <= T; tc++) { N = sc.nextInt(); K = sc.nextInt(); M = sc.nextInt(); R = new int[18]; Ans = 9999; for (int i = 0; i < N; i++) { R[i] = sc.nextInt(); } backTrack(0, 0); System.out.print("#" + tc); if (Ans == 9999) { System.out.println(" -1"); } else { System.out.println(" " + Ans); } } } private static void backTrack(int k, int count) { if (count >= Ans) { return; } if (k == N) { if (!biBat()) { if (count < Ans) { Ans = count; } } return; } for (int i = 0; i <= 1; i++) { if (i == 0) { backTrack(k + 1, count); } else { R[k] += 1; backTrack(k + 1, count + 1); R[k] -= 1; } } } static boolean biBat() { for (int i = 0; i <= N - K; i++) { int count = 0; int max = findMax(i, i + K); for (int j = i; j < i + K; j++) { if (R[j] == max) { count++; } } if (count >= M) { return true; } } return false; } private static int findMax(int i, int j) { int max = 0; for (int k = i; k < j; k++) { max = Math.max(max, R[k]); } return max; } }
Editor is loading...
Leave a Comment