Untitled
plain_text
a month ago
1.9 kB
1
Indexable
Never
package chu_voi_nho; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static int N, K, M, res; static int[] a, max, dem; static void findmax() { max = new int[N - K + 1]; dem = new int[N - K + 1]; for (int i = 0; i < N - K + 1; i++) { int count = 0; int tmp = a[i]; for (int j = i; j < i + K; j++) { if (a[j] > tmp) { tmp = a[j]; count = 1; } else if (a[j] == tmp) { count++; } } max[i] = tmp; dem[i] = count; } } static void backtrack(int k, int count) { if (k == N) { findmax(); int check = 0; for(int i = 0; i <N-K+1;i++){ if(dem[i] >= M){ check = 1; break; } } if (check == 0) { res = Math.min(res, count); } return; } if (count >= res) { return; } for (int i = 0; i < 2; i++) { a[k] += i; backtrack(k + 1, count + i); a[k] -= i; } } public static void main(String[] args) { try { System.setIn(new FileInputStream("input.txt")); } catch (FileNotFoundException e) { // TODO Auto-generated catch block e.printStackTrace(); } Scanner scanner = new Scanner(System.in); int test = scanner.nextInt(); for (int t = 1; t <= test; t++) { N = scanner.nextInt(); K = scanner.nextInt(); M = scanner.nextInt(); a = new int[N]; for (int i = 0; i < N; i++) { a[i] = scanner.nextInt(); } res = Integer.MAX_VALUE; // for (int i = 0; i < N - K + 1; i++) { // System.out.print(max[i] + " "); // } // System.out.println(); // // for (int i = 0; i < N - K + 1; i++) { // System.out.print(dem[i] + " "); // } // System.out.println(); if (M == 1) { res = -1; } else { backtrack(0, 0); } System.out.println("#" + t + " " + res); } scanner.close(); } }