Untitled
unknown
plain_text
a year ago
1.4 kB
6
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