搜索

问题描述 有N根木棍，需要将其粘贴成M个长木棍，使得最长的和最短的的差距最小。 输入格式 第一行两个整数N,M。 一行N个整数，表示木棍的长度。 输出格式 一行一个整数，表示最小的差距 样例输入 3 2 10 20 40 样例输出 10 数据规模和约定 N, M<=7 只通过了百分之90 的案例 7 个的时候超时了 俺也不知到如何优化 import java.util.Scanner; public class Main { static int min_sub; // 最小的差距 public static void main(String[] args) { // TODO Auto-generated method stub int[] mg; int[] mg_flag ; int[] D_length ; min_sub = 700000; int M , N ; // N 木棍 M 几段 Scanner sc= new Scanner(System.in); N = sc.nextInt(); M = sc.nextInt(); mg = new int[N]; mg_flag = new int[N]; D_length = new int[M]; for (int i = 0; i < mg.length; i++) { mg[i] = sc.nextInt(); } dfs(N,mg,mg_flag,D_length); System.out.println(min_sub); } static void dfs(int dd,int[] mg, int[] mg_flag,int[] D_length ) { if(dd == 0) { // 分完了 检测当前的 最大插差值 if(min_sub>=getNowChazhi(D_length)) { min_sub = getNowChazhi(D_length); return ; } } // 开始分了 for (int i = 0; i < mg.length ; i++) { // 首先要分的棍子必须是没被分过的 if(mg_flag[i]==0){ // 都给谁呢？ 0 - M -1 for (int j = 0; j < D_length.length; j++) { mg_flag[i]=1; // 用过了 D_length[j] += mg[i]; dfs(dd-1,mg,mg_flag,D_length); D_length[j] -= mg[i]; mg_flag[i]=0; // 回溯 } } } } static int getNowChazhi(int[] D_length) { int max = 0; int min = 70000000; for (int i = 0; i < D_length.length; i++) { if(max<D_length[i]) max = D_length[i]; if(min>D_length[i]) min = D_length[i]; } return Math.abs(max-min); } }