小爱和小溪有N个数字,他们两个想公平的分配这些数字。小爱拿的数字集合为I=「i1, i2, ik」,小溪获得剩下的J,J=「j1, j2, jn-k」。但是他们衡量分配公平与否的原则与众不同:
在小爱拿到其中的K个数字的前提下,计算出他们分配偏差f(I)的最小值。
小爱和小溪有N个数字,他们两个想公平的分配这些数字。小爱拿的数字集合为I=「i1, i2, ik」,小溪获得剩下的J,J=「j1, j2, jn-k」。但是他们衡量分配公平与否的原则与众不同:
在小爱拿到其中的K个数字的前提下,计算出他们分配偏差f(I)的最小值。
输入第一行两个数字,分别表示总的数字量N和小爱拿的数字量K。第二行有N个数字,表示每个数字的值。
输出一个数字,表示分配偏差f(I)的最小值。
4 1 3 3 3 1
2
import java.util.Scanner; /* * @author Moze 2020 * 此题目题量较小,使用穷举法可以求解。 * 递归出共有2的N次方种情况,可以进行一些剪枝 * 我只减去了最后小爱个数不等于k的就可以了 * 注:个人感觉此题不能够用动态规划吧。 * 原因:设index为止,小爱分了i个数,和index时刻小爱分了i个数还是i-1个数 并不能直接联系,必须等到最后时刻才能够确定 */ public class Main { static int N; static int a[]; static int k; static int min=Integer.MAX_VALUE; public static void main(String[] args) { Scanner aa= new Scanner(System.in); N = aa.nextInt(); k = aa.nextInt(); a=new int[N]; for(int i=0;i<N;i++){ a[i]=aa.nextInt(); } m(0,new int[N],new int[N],0,0); System.out.println(min); } public static void m(int index,int[] xi,int[] ai,int num_xi,int num_ai){ if(index == N){ if(num_ai != k){ return ; } int sum=0; for(int i=0;i<num_ai;i++){ for(int j=0;j<num_xi;j++){ sum+=Math.abs(ai[i]-xi[j]); } } min = Math.min(min, sum); return ; } if(num_ai<k){ ai[num_ai]=a[index]; m(index+1,xi,ai,num_xi,num_ai+1); } xi[num_xi]=a[index]; m(index+1,xi,ai,num_xi+1,num_ai); } }