种树

import java.util.*;

/**
 * 深度遍历，优先选择种类小的树
 **/

public class Main {
    private static boolean dfs(int[] curr, int index, int[] arr, int last) {
        int rest = curr.length - index;
        if (rest == 0) {
            for (int i : curr)    System.out.print(i + 1 + " ");
            return true;
        }
        
        for (int tree : arr) {
            if (tree > (rest + 1) / 2)    return false;
        }
        
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != 0 && i != last) {
                int[] temp = new int[arr.length];
                System.arraycopy(arr, 0, temp, 0, arr.length);
                temp[i]--;
                int[] currTemp = new int[curr.length];
                System.arraycopy(curr, 0, currTemp, 0, curr.length);
                currTemp[index] = i;
                if (dfs(currTemp, index + 1, temp, i))    return true;
            }
        }
        
        return false;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        int[] arr = new int[count];
        int total = 0;
        for (int i = 0; i < count; i++) {
            int temp = scanner.nextInt();
            arr[i] = temp;
            total += temp;
        }
        scanner.close();
        
        int[] curr = new int[total];
        if (!dfs(curr, 0, arr, -1)) {
            System.out.println("-");
        }
    }
}

思路：
使用搜索来做，但纯粹使用搜索的话通过率为90%，有一个点会超时，所以需要剪枝，一个简单的剪枝思路是比较当前未种的树和坑的大小关系！
具体的剪枝思路是每次搜索之前判断当前剩余的坑位left和任意品种的树之间的关系:

1) 如果left为偶数，那么只要tree[i] > left / 2，就表示肯定种不了
2) 如果left为奇数，那么只要tree[i] > (left + 1) / 2，就表示肯定种不了
这里有一个小技巧：left为偶数时，left/2 和(left + 1)/2的值是相等的，所以可以统一使用tree[i] > (left+1)/2的关系来做剪枝优化！

import java.util.*;

public class Main {

    static int n, m;
    static int[] tree;
    static List<String> ans;

    static boolean check(int left) {
        for (int i = 1; i <= n; i++) {
            if (tree[i] > (left + 1) / 2) return false;
        }
        return true;
    }

    static boolean dfs(int idx) {
        if (!check(m - idx)) return false;
        if (idx == m) {
            return true;
        } else {
            for (int i = 1; i <= n; i++) {
                if (idx == 0 || (tree[i] != 0 && i != Integer.valueOf(ans.get(idx - 1)))) {
                    tree[i]--;
                    ans.add(i + "");
                    if (dfs(idx + 1)) return true;
                    ans.remove(ans.size() - 1);
                    tree[i]++;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            n = sc.nextInt();
            tree = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                tree[i] = sc.nextInt();
                m += tree[i];
            }
            ans = new ArrayList<>();
            if (dfs(0)) {
                System.out.println(String.join(" ", ans));
            } else {
                System.out.println("-");
            }
        }
    }
}

importjava.util.Scanner;

//1、首先判断能不能种树。如果是奇数，如果某种树大于（M+1）的一半则不能种，

如果是偶数，则大于M的一半不能种树

// 2、每次种树前都要判断是不是某种树大于一半，如果是，本次种该树。

如果不是再从下网上遍历数组，优先种序号小的树（要保证该序号的树还有的剩，且不等于之前种的树）

publicc***in {

publicstaticvoidmain(String[] args) {

Scanner input =newScanner(System.in);

intN=input.nextInt();

int[] nums=newint[N];

intM=0;

for(inti = 0; i <N ; i++) {

nums[i]=input.nextInt();

M+=nums[i];

}

if(M%2==0){//如果是偶数

for(inti = 0; i <N ; i++) {

if(nums[i]>M/2){

System.out.println("-");

return;

}

}

}else{//如果是奇数

for(inti = 0; i <N ; i++) {

if(nums[i]>(M+1)/2){

System.out.println("-");

return;

}

}

}

StringBuffer res=newStringBuffer();

intcount=M;

intpre=-1;

for(inti=0;i<M;i++){

booleanflag=false;

for(intk=0;k<N;k++){

if(nums[k]>count/2){//判断是否有树大于剩余的一半

res.append(k+1);

res.append(" ");

nums[k]--;

pre=k+1;

flag=true;

count--;

break;

}

}

if(flag==true) continue;

intj=0;

while(nums[j]==0||(j+1)==pre){

j++;

}

nums[j]--;

pre=j+1;

res.append(j+1);

res.append(" ");

count--;

}

System.out.println(res.toString().trim());

}

}