调整数组使差最小
Description 有两个序列 a,b，大小都为 n,序列元素的值任意整数，无序； 要求：通过交换 a,b 中的元素，使[序列 a 元素的和]与[序列 b 元素的和]之间的差最小。 Input 输入第一行为用例个数， 每个测试用例输入为两行，分别为两个数组，每个值用空格隔开。 Output 输出变化之后的两个数组内元素和的差绝对值。 Sample Input 1 1 100 99 98 1 2 3 1 2 3 4 5 40 Sample Output 1 48
思路一：暴力求解。将a数组中元素与b数组中元素一一进行交换，每一次交换后后对2个数组的绝对值差进行重新计算，依次进行，直至求出一个最小的差值。然而事实是一直WA，因为这样只能保证每次a,b只有一对进行交换，实际上有的时候需要同时交换2对才能得到最优解。那么就pass了。
思路二：利用递归求解。我们可以这样想，由于a和b数组元素个数是相同的，那么我们就相当于把a和b所有元素分成2部分，使得这2部分的差值最小。即从2*N元素里面去挑出N个数去满足这样的条件。那么我们很容易想到用递归去做，填充n个格子，并不断对得到的n格子进行判断，从而得到满足最小的差值的格子。看代码吧：
import ja.util.*; public class Main { static Scanner in = new Scanner(System.in); static int diff,n,sums; static int[] arr; static void solve(int index,int sum,List st){ if(st.size()>=n){ int tempDiff = Math.abs(sums - 2*sum); diff = Math.min(diff,tempDiff); return; } for (int i = index; i < 2*n; i++) { st.add(arr[i]); sum += arr[i]; solve(i+1,sum,st); sum -= arr[i]; st.remove(st.size()-1); } } public static void main(String[] args) { int t = in.nextInt(); while(t-->0){ in.nextLine(); String[] s1 = in.nextLine().split(" "); n = s1.length; int sumA = 0,sumB = 0; int[] a = new int[n]; int[] b = new int[n]; arr = new int[2*n]; for (int i = 0; i < s1.length; i++) { a[i] = Integer.parseInt(s1[i]); sums += a[i]; sumA += a[i]; arr[i] = a[i]; } for (int i = 0; i < n; i++) { b[i] = in.nextInt(); sums += b[i]; sumB += b[i]; arr[i+n] = b[i]; } diff = Math.abs(sumA-sumB); solve(0,0,new ArrayList()); System.out.println(diff); } } }