題意
鏈接：https://www.nowcoder.com/questionTerminal/52f25c8a8d414f8f8fe46d4e62ef732c
來源：牛客網
小多想在美化一下自己的莊園，他的莊園毗鄰一條小河，他希望在河邊種一排樹，共 M 棵，小多采購了 N 個品種的樹，每個品種的數量是 Ai (樹的總數量恰好為 M)，但是他希望任意兩棵相鄰的樹不是同一品種的，小多請你幫忙設計一種滿足要求的種樹方案，
輸入描述:
第一行包含一個正整數 N，表示樹的品種數量，
第二行包含 N 個正整數，第 i (1 <= i <= N) 個數表示第 i 個品種的樹的數量，
資料范圍：
1 <= N <= 1000
1 <= M <= 2000
輸出描述:
輸出一行，包含 M 個正整數，分別表示第 i 棵樹的品種編號 (品種編號從1到 N)，若存在多種可行方案，則輸出字典序最小的方案，若不存在滿足條件的方案，則輸出"-"，
思路
直接搜索，看上去復雜度是階乘級，但剪枝后就能過了，玄學，剪枝點是當出現一種樹的數量大于剩余樹的1/2時，就不滿足條件了，
代碼
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static final int N = 1005;
static int[] a = new int[N];
static int m=0,n,flag=0;
static List<Integer> ans=new ArrayList<Integer>();
static void dfs(int cnt) {
for(int i=1;i<=n;i++) {
if(a[i]>(m-cnt+1)/2)
return ;
}
if(cnt==m) {
flag=1;
return ;
}
for(int i=1;i<=n;i++) {
if(cnt==0||(a[i]>0&&ans.get(ans.size()-1)!=i)) {
a[i]--;
ans.add(i);
dfs(cnt+1);
if(flag==1)
return ;
ans.remove(ans.size()-1);
a[i]++;
}
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
for (int i = 1; i <= n; i++) {
a[i] = in.nextInt();
m += a[i];
}
dfs(0);
if(flag==1) {
for(int i:ans) {
System.out.print(i+" ");
}
System.out.println();
}else {
System.out.println("-");
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/114598.html
標籤：其他