素数的个数

给出一个包含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]);
}