素数的个数

给出一个包含n个正整数的数组a，把a[i]拆分为若干个和为a[i]的素数，求拆分后最多能有多少个素数。

第一行数据为n，表示数组长度，第二行为n个元素。
输入
3
1 1 1
输出
0 1不可拆分
输入
1 3 5 7
6 1为0个，3为1个，5为（2,3），7为（2,2,3）

分析：
这道题比较简单，当a[i]>1的时候，素数的个数为a[i]/2。但是要注意原题目的数据范围比较大，最后的总个数可能超出Int上限需要用Long来存，具体代码如下：

public static void main(String[] args){Scanner scan = new Scanner(System.in);int n = scan.nextInt();int[] a = new int[n];for(int i=0;i<n;i++){a[i] = scan.nextInt();}System.out.println(chaifen(a));
}
public static long chaifen(int[] a){long count = 0;for(int i=0;i<a.length;i++){if(a[i] == 1)continue;else{count+=a[i]/2;}}return count;
}

字典序最小的排列

给出一个长度为m的序列T，求一个长度为n且字典序最小的排列S，要求不改变原序列中元素的相对位置。

第一行输入两个正整数n和m
第二行输入m个数，表示序列
5 3
2 1 5
输出
2 1 3 4 5

分析：这道题我采用归并排序的思路，首先枚举出T中多出来的元素，比如题目中的T相比S就多出来了3 4。
然后对两个数组2 1 5和3 4进行归并排序，具体代码如下：

public static void main(String[] args){Scanner scan = new Scanner(System.in);int n = scan.nextInt();int m = scan.nextInt();int[] s = new int[m];for(int i=0;i<m;i++){s[i] = scan.nextInt();}int[] t =a(s,n);for(int i=0;i<t.length-1;i++){System.out.print(t[i]);System.out.print(" ");}System.out.print(t[n-1]);System.out.print("\n");
}
public static int[] a(int[] s,int n){int[] t = new int[n];int m = s.length;int[] tmp = new int[n-m];HashSet<Integer> set = new HashSet<>();for(int i:s){set.add(i);}int index=1;for(int i=0;i<tmp.length;i++){while(set.contains(index))index++;tmp[i] = index++;}int index1 = 0;int index2 = 0;for(int i=0;i<t.length;i++){if(index1 <m && index2<n-m){if(s[index1] <= tmp[index2]){t[i] = s[index1++];}else{t[i] = tmp[index2++];}}else if(index1<m){t[i] = s[index1++];}else{t[i] = tmp[index2++];}}return t;
}

丢弃最少物品

给出n个物品，每个物品都有自己的价值，每个物品只有一件，这些物品需要分给两个人，要求分配完之后，两个人的物品价值相同。分配完成之后，会丢弃剩下的物品，求最少要丢弃多少物品。

输入
输入第一行为总的测试数据个数，第二行为物品个数n，第三行为n个物品的价值。
1
5
30 60 5 15 30
输出
20 丢弃5和15，把60分配给第一个人，2个30分配给第二个人。

分析：这道题我一开始想用背包做，但是不知道怎么计算背包的容量，所以就想着先用回溯过几个用例再说，结果没想到直接过了。
不知道有没有大神能够提供最优解。

static int res;
public static void main(String[] args) {Scanner scan = new Scanner(System.in);int t = scan.nextInt();while(t-->0){res = Integer.MAX_VALUE;int n = scan.nextInt();int[] item = new int[n];for(int i =0;i<n;i++)item[i] = scan.nextInt();a3(item, 0,0,0, 0);System.out.println(res);}
}
public static void a3(int[] item,int index,int x,int y,int r){if(index == item.length){if(x == y)res = Math.min(r,res);return;}a3(item,index+1,x+item[index],y,r)a3(item,index+1,x,y+item[index],r);a3(item,index+1,x,y,r+item[index]);
}

差距最小的生成树

给出一个无向图，一共有n个点，m条边，每条边的权值为v。
求一个生成树，使得图保持联通的同时，权值的最大值和最小值之差最小。

输入
第一行为n和m，表示点的个数和边的条数
后面为m行，表示m条边的两个顶点和其权值
3 5
1 2 10
1 3 5
3 1 12
2 3 19
1 2 74
输出
2 选择边1和3，最小差值为12-10

分析：不会。

后记

总的来说这次运气比较好，A了3题，最后一题确实不会做，3题应该能进面试了吧，接下来好好准备阿里和雷火的面试吧。

---