首页 > 试题广场 > 种树
[编程题]种树
  • 热度指数:6895 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
小多想在美化一下自己的庄园。他的庄园毗邻一条小河,他希望在河边种一排树,共 M 棵。小多采购了 N 个品种的树,每个品种的数量是 Ai (树的总数量恰好为 M)。但是他希望任意两棵相邻的树不是同一品种的。小多请你帮忙设计一种满足要求的种树方案。

输入描述:
第一行包含一个正整数 N,表示树的品种数量。
第二行包含 N 个正整数,第 i (1 <= i <= N) 个数表示第 i 个品种的树的数量。
数据范围:
1 <= N <= 1000
1 <= M <= 2000


输出描述:
输出一行,包含 M 个正整数,分别表示第 i 棵树的品种编号 (品种编号从1到 N)。若存在多种可行方案,则输出字典序最小的方案。若不存在满足条件的方案,则输出"-"。
示例1

输入

3
4 2 1

输出

1 2 1 2 1 3 1

修改了很久
我觉得以上答案不够完美,有些很繁琐

#include <bits/stdc++.h>
using namespace std;

bool dfs(vector<int>& nums, vector<int>& results, int m, int prev) 
{
    if (m == 0) {
        return true;
    }

    for (int i = 0; i < nums.size(); ++i) {

        if ( nums[i] * 2 >  m + 1) {
            return false;
        }

        if (nums[i] && prev != i) {

            nums[i]--;
            results.push_back(i);

            if ( dfs(nums, results, m - 1, i) ) {
                return true;
            }

            results.pop_back();
            nums[i]++;
        }
    }

    return false;
}

int main() 
{
    int n, m ;
   
    cin >> n;

    vector<int>  nums(n), results;

    m = 0;
    for (int i = 0; i < n; ++i) {
       cin >> nums[i];
       m += nums[i];
    }

    if (dfs(nums, results, m, -1) ) {
        for (auto c : results) {
            cout << c + 1 <<" ";
            // 下标为 1 - n  而存储的是 0 - n - 1 即数组下标
        }
        cout << endl;
    } else {

        cout<<"-"<<endl;

    }

    return 0;
}


编辑于 2020-06-23 23:38:17 回复(9)

思路:
使用搜索来做,但纯粹使用搜索的话通过率为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("-");
            }
        }
    }
}
编辑于 2019-07-22 10:14:58 回复(4)

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());

}

}

编辑于 2019-05-14 21:34:27 回复(1)
/*
DFS,需要判断不成立的情况下剪枝
*/
#include <bits/stdc++.h>
using namespace std;

int idx_max(int a[], int n)
{// 找出a中最大值的下标
    int idx = -1, t_max = 0;
    for(int i = 0; i < n; i++) {
        if(a[i] > t_max) {
            idx = i;
            t_max = a[i];
        }
    }
    return idx;
}
bool dfs(int a[], int b[], int n, int &m, int step)
{
    int idx = idx_max(a, n);
    if(idx == -1) return true;
    if(a[idx] * 2 > m + 1) return false; //剪枝
    if(a[idx] * 2 == m + 1) { //有上一句剪枝,可不用此步
        a[idx]--;
        m--;
        b[step] = idx + 1; //此情况只有一种正确选择
        if(dfs(a, b, n, m, step + 1)) return true;
        a[idx]++;
        m++;
    } else {
        for(int i = 0; i < n; i++) {
            if(a[i] > 0 && (step == 0 || b[step - 1] != i + 1)) {
                a[i]--;
                m--;
                b[step] = i + 1;
                if(dfs(a, b, n, m, step + 1)) return true;
                a[i]++;
                m++;
            }
        }
    }
    return false;
}

int main(void)
{
    //freopen("input.txt", "r", stdin);
    int n, m = 0;
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        m += a[i];
    }
    int b[m], t_sum = m;
    if(dfs(a, b, n, t_sum, 0)) {
        for (int i = 0; i < m; i++) {
            printf("%d ", b[i]);
        }
    } else printf("-");
    return 0;
}

编辑于 2019-07-18 13:15:53 回复(6)
#include <stdio.h>

int a[1003];
int ret[2003];
int n;

int dfs(int step, int have) {
  if (have == 0) return 1;
  int i;
  for (i = 1; i <= n; i++) {
    if (a[i] > (have - a[i] + 1)) return 0;
    if (a[i] <= 0) continue;
    if (step == 0 || ret[step - 1] != i) {
      ret[step] = i;
      a[i]--;
      if(dfs(step + 1, have - 1)) return 1;
      a[i]++;
    }
  }
}

int main() {
  int sum = 0;
  int i;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%d", a + i);
    sum += a[i];
  }
  if (dfs(0, sum)) {
    for (i = 0; i < sum; i++) {
      printf("%d ", ret[i]);
    }
    printf("\n");
  } else {
    printf("-\n");
  }
  return 0;
}

发表于 2019-11-23 20:21:58 回复(0)
#include <bits/stdc++.h>
using namespace std;

bool DFS(vector<int> &a, vector<int> &b, int &t, int x){
    if(t==0)
        return true;
    for(int i=1;i<=a.size();i++){
        if(a[i]*2>t+1)
            return false;
        if(a[i]>0 && i!=x){
            a[i]--;
            t--;
            b.push_back(i);
            if(DFS(a, b, t, i))
                return true;
            b.pop_back();
            t++;
            a[i]++;
        }
    }
    return false;
}

int main(){
    int n, s=0;
    cin>>n;
    vector<int> a(n+1);
    vector<int> b;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s += a[i];
    }
    int t = s;
    if(DFS(a, b, t, 0)){
        for(int i=0;i<s;i++){
            if(i==s-1)
                cout<<b[i]<<endl;
            else
                cout<<b[i]<<" ";
        }
    }else{
        cout<<"-"<<endl;
    }
    return 0;
}

发表于 2019-08-16 13:51:06 回复(0)
深搜求解,注意当一种树的总数超过剩余树的一半时,肯定没法完成所有相邻的树品种都不同,利用这个条件进行剪枝。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;

public class Main {
    static ArrayList<Integer> scheme = new ArrayList<>();     // 方案数组,第i个元素表示第i个位置放置的树的品种编号
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        int m = 0;
        String[] strArr = br.readLine().trim().split(" ");
        int[] treeType = new int[n];
        for(int i = 0; i < n; i++) {
            treeType[i] = Integer.parseInt(strArr[i]);
            m += treeType[i];
        }
        if(dfs(treeType, m, -1)){
            // 存在可行方案
            for(int i = 0; i < scheme.size(); i++)
                System.out.print((scheme.get(i) + 1) + " ");
        }else
            System.out.println("-");
    }
    
    private static boolean dfs(int[] treeType, int m, int prev) {
        if(m == 0) return true;    // 树用完了,返回true
        for(int i = 0; i < treeType.length; i++){
            if(treeType[i]*2 > m + 1)     // 剪枝,某一种类型的树大于总数的一半肯定无法达成相邻树的品种不同
                return false;
            if(treeType[i] > 0 && prev != i) {
                // 如果i品种的树还有,且前一棵树不是i品种,就在本位置种植品种i的树
                treeType[i]--;
                scheme.add(i);
                if(dfs(treeType, m - 1, i)) return true;
                // 回溯
                scheme.remove(scheme.size() - 1);
                treeType[i]++;
            }
        }
        return false;
    }
}


发表于 2021-02-01 14:54:42 回复(0)
/*DFS+剪枝 */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int>ans;
bool flag;
/* n:树的种类  m:还有多少树没有种  last:上一棵树种的是哪一个*/
void Dfs(int *a, int n, int m, vector<int>ans, int last){
    if(m==0){
        for(int i=0; i<ans.size(); i++){
            printf("%d%c", ans[i], i==(ans.size()-1)?'\n':' ');
        }
        flag=true;
        return;
    }
    for(int i=1; i<=n; i++){//剪枝
        if(a[i]>(m+1)/2) return;
    }
    for(int i=1; i<=n; i++){
        if(a[i]>0 && i!=last){
            a[i]--, ans.push_back(i);
            if(!flag) Dfs(a, n, m-1, ans, i);
            a[i]++, ans.pop_back();
        }
    }
}

int main(){
    int n, m;
    int a[1005];
    while(~scanf("%d", &n)){
        m=0;
        for(int i=1; i<=n; i++) scanf("%d", &a[i]), m+=a[i];
        ans.clear();
        flag=false;//全局变量标记是否找到最优解
        Dfs(a, n, m, ans, -1);
        
        if(!flag) printf("-\n");
    }
    return 0;
}

发表于 2020-07-23 00:24:37 回复(0)
/*
贪心递归
首先判断是否可行:只要最多的一种树的数量*2<所有树的总量+1,就肯定有可行解
对于可行解,我们每一次种树的时,只需要考虑:
  1.从编号小到大遍历,找到第1个数量不为0且和前一颗树编号不同的编号
  2.1 若这种树是目前最多的树,中了它
  2.2 若这种树不是目前最多的,但中了它之后剩下的树仍可行,中了它
  2.3 若这种树不是目前最多的,中了它后就不可行了,那别说啥了,找到目前最多的那种,中了它
(写完感觉这个判断条件逻辑的内外层应该反过来= =有空再改吧)
*/

#include<iostream>
#include<vector>
using namespace std;

vector<int> fun(vector<int> &v, int maxv, int sumv, int pre) {
    vector<int> res;

    int i = 0;
    while(v[i] == 0 || i == pre) {
        i++;
    }
    if(sumv == 1) {
        res.push_back(i+1);
        return res;
    }
    else {
        if(v[i] == maxv) {
            v[i]--;
            maxv = maxv - 1;
            for(int j = i+1; j < v.size(); j++) {
                maxv = max(maxv, v[j]);
            }
            res = fun(v, maxv, sumv-1, i);
            res.insert(res.begin(),i+1);
            return res;
        }
        else {
            if(maxv*2 < sumv + 1){
                v[i]--;
                res = fun(v, maxv, sumv-1, i);
                res.insert(res.begin(),i+1);
                return res;
            }
            else{
                while(v[i] != maxv || i == pre) {
                    i++;
                }
                v[i]--;
                maxv = maxv - 1;
                for(int j = i+1; j < v.size(); j++) {
                    maxv = max(maxv, v[j]);
                }
                res = fun(v, maxv, sumv-1, i);
                res.insert(res.begin(),i+1);
                return res;
            }
        }
    }
}

int main() {
    int N;
    cin>>N;
    int tmp;
    vector<int> v;
    vector<int> res;
    int maxv = 0, sumv = 0;
    for(int i = 0; i < N; i++) {
        cin>>tmp;
        v.push_back(tmp);
        maxv = maxv > tmp ? maxv:tmp;
        sumv = sumv + tmp;
    }
    
    if(maxv*2 > sumv + 1) {
        cout<<"-"<<endl;
        return 0;
    }
    res = fun(v, maxv, sumv, -1);
    for(int i = 0; i < res.size() - 1; i++) {
        cout<<res[i]<<" ";
    }
    cout<<res[res.size()-1];
    
    return 0;
}

发表于 2020-06-28 17:46:24 回复(0)

全用深搜,数据一大就凉。
其实贪心就可以搞定(当然debug了比较久,在那个判断一定要种的条件上)
先判断是否一定要种剩余数量最多的树(判断条件是【最大树数量为奇数&&(剩余树数量+1)/2==最大树数量】);一定要种的话,再判断是否上一棵树序号相同,相同就选数量第二多的数(其实这样下一步就已经能确定无法满足条件了)。
不是一定的话就选序号最小的树种,上一次种过么就选第二小的。
有问题的话欢迎指出

#include<iostream>
(720)#include<vector>
#include<string>

using namespace std;

int N;
int number[4000];
int res[4000];
int main(){
    cin >> N;
    int M = 0;
    for(int i = 0 ; i < N; i++){
        int tmp ;
        cin >> tmp;
        M += tmp;
        number[i] = tmp;
    }
    for(int i = 0 ; i < M; i++){
        int max_tree = -1;
        int max_number = 0;
        int max2_tree = -1;
        int max2_number = 0;
        for(int j = 0 ; j < N; j++){
            if(number[j] > max_number){

                // 存第二大的,之前最大总是大于第二大
                max2_number = max_number;
                max2_tree = max_tree;

                max_number = number[j];
                max_tree = j;
            }
            else{
                if(number[j] > max2_number){
                    // 存第二大的
                    max2_number = number[j] ;
                    max2_tree = j;
                }
            }


        }
        int remain = M- i;
        if((remain+1)/2 < max_number){
            cout<< "-" << endl;
            return 0;
        }
        // 只能种这个树
        int test = 0;
        if(remain%2 == 1 &&  (remain+1)/2 == max_number){
            // 相邻不是一种树
            if(i == 0 || (i > 0 && res[i-1] != max_tree)){
                res[i] = max_tree;
                number[max_tree]--;
            }
            else{
                res[i] = max2_tree;
                number[max2_tree]--;

            }

        }
        else{
            int j, j2;
            for(j = 0 ; j < N && !number[j]; j++){}
            for(j2 = j+1 ; j2 < N && !number[j2]; j2++){}
            if(i == 0 || (i > 0 && res[i-1] != j)){
                res[i] = j;
                number[j]--;
            }
            else{
                res[i] = j2;
                number[j2]--;
            }
        }


    }
    for(int i = 0 ; i < M; i++){
        cout << res[i]+1;
        if(i != M-1) cout << " ";
        else cout << endl;
    }

    return 0;

}
发表于 2020-05-03 23:59:22 回复(1)
python 解法
import sys # python 默认递归深度不超过1000,做dfs会比C吃亏
sys.setrecursionlimit(10000000)# 手动修改深度,如果TLE那就是算法的问题

# 小多采购了 N 个品种的树,每个品种的数量是 Ai (树的总数量恰好为 M)
N = int(input())
arr = list(map(int, input().split())) # sum(arr) = M
M = sum(arr)
res = []


def dfs(a, m, pre_tree_class):
    if m == 0:
        return True
    for i in range(len(a)):
        tree_class = i+1
        if a[i]*2 > m+1:
            return False
        if a[i]>0 and pre_tree_class != tree_class:
            a[i] -= 1
            res.append(tree_class)
            if dfs(a, m-1, tree_class):
                return True
            res.pop(-1)
            a[i] += 1
    return False

try:
    if dfs(arr, M, 0):
        print(" ".join(map(str, res)))
    else:
        print("-")
except Exception as e:
    print(e)


编辑于 2020-04-25 22:22:31 回复(1)
package 种树;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/*
 * 小多想再美化一下自己的庄园。他的庄园毗邻一条小河,他希望在河边种一排树,共 M 棵。
 * 小多采购了 N 个品种的树,每个品种的数量是 Ai (树的总数量恰好为 M)。
 * 但是他希望任意两棵相邻的树不是同一品种的。
 * 小多请你帮忙设计一种满足要求的种树方案。
 * 
 * 输入描述:
 * 第一行包含一个正整数 N,表示树的品种数量。
 * 第二行包含 N 个正整数,第 i (1 <= i <= N) 个数表示第 i 个品种的树的数量。
 * 数据范围:1 <= N <= 1000,1 <= M <= 2000
 * 
 * 输出描述:
 * 输出一行,包含 M 个正整数,分别表示第 i 棵树的品种编号 (品种编号从1到 N)。
 * 若存在多种可行方案,则输出字典序最小的方案。
 * 若不存在满足条件的方案,则输出"-"。
 * 
 * 示例1
 * 输入
 * 3
 * 4 2 1
 *
 * 输出
 * 1 2 1 2 1 3 1
 */

/*
 * 算法:DFS、剪枝优化
 * 数据结构:ArrayList
 * 剪枝思路:每次搜索之前判断当前剩余的空间大小和任意品种的树之间的关系:
 * 1) 如果freeSpaceSize为偶数,那么只要treeQuantityArray[treeCategory] > freeSpaceSize / 2,就不能保证相邻树种不同
 * 2) 如果freeSpaceSize为奇数,那么只要treeQuantityArray[treeCategory] > (freeSpaceSize + 1) / 2,就不能保证相邻树种不同
 * tip:freeSpaceSize为偶数时,treeQuantityArray[treeCategory] > freeSpaceSize / 2 和treeQuantityArray[treeCategory] > (freeSpaceSize + 1) / 2的值是相等的。
 * 所以可以统一使用treeQuantityArray[treeCategory] > (freeSpaceSize + 1) / 2的关系来做剪枝优化!
 */
public class Main {
	
	//剩余空间大小是否能保证,在相邻树种不同的情况下,能放下任意品种的树(够放最大数量的树种)
	private static boolean checkIfFreeSpaceEnough(int treeCategorySize, int[] treeQuantityArray, int freeSpace) {
		for (int treeCategory = 1; treeCategory <= treeCategorySize; treeCategory++) {
			if (treeQuantityArray[treeCategory] > (freeSpace + 1) / 2) {
				return false;
			}
		}
		return true;
	}
	
	//深度优先搜索,寻找是否存在按规则分布的序列
	private static boolean DFS(int treeDistributionIndex, int[] treeQuantityArray, int treeCategorySize, 
											 List<String> treeDistributionList, int treeQuantitySum) {
		//形成按规则分布的序列,DFS成功标志
		if (treeDistributionIndex == treeQuantitySum) {
			return true;
		}
		//剩余空间是否充足,剩余空间即剩下要放的树的数量
		int freeSpace = treeQuantitySum - treeDistributionIndex;
		if (! checkIfFreeSpaceEnough(treeCategorySize, treeQuantityArray, freeSpace)) {
			return false;
		}
		for (int treeCategory = 1; treeCategory <= treeCategorySize; treeCategory ++) {//字典序实现
			//treeQuantityArray[treeCategory] != 0表示某一树种不用尽
        	//treeCategory != Integer.valueOf(treeDistributionList.get(treeDistributionIndex - 1))表示相邻树种不该相同
			if (treeDistributionIndex == 0 || 
				treeQuantityArray[treeCategory] != 0 && 
				treeCategory != Integer.valueOf(treeDistributionList.get(treeDistributionIndex - 1))) {
				treeQuantityArray[treeCategory] --;
				//int值+""->String
				treeDistributionList.add(treeCategory + "");
				if (DFS(treeDistributionIndex + 1, treeQuantityArray, treeCategorySize, treeDistributionList, treeQuantitySum)) {
					return true;
				}
				//某一条分路走不下去返回false了(放树顺序错了,如放该种树后面数目更大的树种将放不下)
                //回退,跳过该树放数目更大的树种
				treeQuantityArray[treeCategory] ++;
				treeDistributionList.remove(treeDistributionList.size() - 1);//将序列末尾值去除
			}
		}
		//无法形成按规则分布的序列,dfs失败标志
		return false;
	}

	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int treeCategorySize = input.nextInt();
		int[] treeQuantityArray = new int[treeCategorySize + 1];
		int treeQuantitySum = 0;
		//题目要求树种从1开始
		for (int treeCategory = 1; treeCategory <= treeCategorySize; treeCategory ++) {
			treeQuantityArray[treeCategory] = input.nextInt();
			treeQuantitySum += treeQuantityArray[treeCategory];
		}
		input.close();
		List<String> treeDistributionList = new ArrayList<String>();
		//若存在按规则分布的序列
		if (DFS(0, treeQuantityArray, treeCategorySize, treeDistributionList, treeQuantitySum)) {
			System.out.println(String.join(" ", treeDistributionList));//分布序列元素间加上空格
		}
		//若不存在按规则分布的序列
		else {
			System.out.println("-");
		}
	}

}

发表于 2020-03-09 20:36:04 回复(0)
#include<iostream>
#include<vector>
using namespace std;
//a为数组,a[i]表示第i个品种的数量,从0开始;b表示最后结果;m为总的数量;prev为前一棵树;
//dfs搜索,没啥问题直接过
bool dfs( vector<int>& a, vector<int>& b, int &m, unsigned prev){
    if(m==0) return true;
    for(int i=0;i<a.size();i++){
        if(2*a[i]>m+1) return false;
        if(a[i]>0&&prev!=i){//a[i]颗树还可以种
            b.push_back(i+1);//种一颗树树
            a[i]--;
            m--;
            if(dfs(a,b,m,i)) return true;//输出最小字典序
            else{
            b.pop_back();
            a[i]++;
            m++;
           }
        }
    }
}

int main()
{
    int n, m = 0;
    cin>>n;
    vector<int> a(n);//第i个品种的树的类目为a[i],树的总类目为n
    for (int i = 0; i < n; i++)
    {
        cin>>a[i];
        m+=a[i];
    }
    vector<int> b;//保存的种树方案
    int m1= m;
    if(dfs(a, b, m1, -1))
    {
        for (int i = 0; i < m; i++)
        {
           cout<<b[i]<<" ";
 
        }
        cout<<endl;
    }
    else
        cout<<"-"<<endl;
    return 0;
}
参考了别的代码,稍微修改了一下,基本思路是dfs
发表于 2019-09-05 12:27:45 回复(0)
主要问题在于剪枝:
如果一种树的个数超过了总数的一半以上,那就不可能成功,需要剪枝
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;

bool ok = false;
int n, m;
vector<int> v, temp, ans;

void dfs(int num, int pre) {
    if (ok) return ;
    if (num == m) {
        ok = true;
        ans = temp;
        return ;
    }
    
    for (int i = 0; i < v.size(); ++i) {
        if (v[i] * 2 > (m-num)+1) {
            return;
        }
        if (pre != (i+1) && v[i] > 0) {
            v[i]--;
            temp.push_back(i+1);
            dfs(num+1, i+1);
            if (ok) return;
            temp.pop_back();
            v[i]++;
        }
    }
}

int main() {
    cin >> n;
    int x;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &x);
        m += x;
        v.push_back(x);
    }
    dfs(0, 0);
    if (ok == false) cout << "-" << endl;
    for (int x : ans) {
        cout << x << " ";
    }
    return 0;
}


发表于 2020-08-02 12:35:17 回复(0)
 
代码复杂了一点,但是空间复杂度和时间复杂度都是O(n)。
举个例子:
输入3   2 4 1
第一轮:1212
第二轮:2还有剩余,插入后面的,121232
第三轮:2还是有剩余,开始在数组中找可插入的点,最后成为212132
struct listNode {
    int val;
    listNode* next;
    listNode(int _val) : val(_val), next(NULL) {};
};

int main() {
    int n;
    while (cin >> n) {
        vector<int> vec(n + 1, 0);
        for (int i = 1; i < n + 1; ++i) {
            int temp;
            cin >> temp;
            vec[i] = temp;
        }
        int total = accumulate(vec.begin(), vec.end(), 0), flag = 0, max;
        total % 2 == 0 ? max = total / 2 : max = total / 2 + 1;
        for (auto x : vec) {
            if (x > max) {
                cout << '-' << endl;
                flag = 1;
            }
        }
        if (flag) continue;

        int t = 0;
        while (vec[t] == 0) {
            t += 1;
        }
        listNode* head = new listNode(t), * tail = head;
        vec[t] -= 1;
        for (int i = 1; i < vec.size(); ++i) {
            int pos = i + 1;
            while (vec[i] != 0 and pos < vec.size()) {
                if (tail->val != i) {
                    while (pos < vec.size() and vec[i] > 0) {
                        if (vec[pos] == 0) continue;
                        while (vec[pos] > 0 and vec[i] > 0) {
                            listNode* temp1 = new listNode(pos);
                            listNode* temp2 = new listNode(i);
                            tail->next = temp2;
                            temp2->next = temp1;
                            tail = temp1;
                            vec[pos] -= 1;
                            vec[i] -= 1;
                        }
                        pos += 1;
                    }
                }
                else {
                    while (pos < vec.size() and vec[i] > 0) {
                        if (vec[pos] == 0) continue;
                        while (vec[pos] > 0 and vec[i] > 0) {
                            listNode* temp1 = new listNode(pos);
                            listNode* temp2 = new listNode(i);
                            tail->next = temp1;
                            temp1->next = temp2;
                            tail = temp2;
                            vec[pos] -= 1;
                            vec[i] -= 1;
                        }
                        pos += 1;
                    }
                }
            }

            if (vec[i] > 0) {
                vector<listNode*> ins;
                listNode* t_head = head;
                while (t_head != NULL) {
                    if (t_head->val != i and (t_head->next == NULL&nbs***bsp;t_head->next->val != i)) {
                        ins.push_back(t_head);
                    }
                    t_head = t_head->next;
                }
                if (ins.size() < vec[i]) {
                    listNode* t1 = new listNode(i);
                    t1->next = head;
                    for (int j = 0; j < ins.size(); ++j) {
                        listNode* t2 = ins[j]->next;
                        listNode* t3 = new listNode(i);
                        ins[j]->next = t3;
                        t3->next = t2;
                    }
                    head = t1;
                }
                else {
                    for (int j = 0; j < ins.size(); ++j) {
                        if (ins.size() - j - 1 > vec[i] and ins[j]->val < i)
                            continue;
                        else {
                            listNode* t5 = ins[j]->next;
                            listNode* t6 = new listNode(i);
                            ins[j]->next = t6;
                            t6->next = t5;
                        }
                    }
                }
            }
        }

        while (head != NULL) {
            cout << head->val << " ";
            head = head->next;
        }
        cout << endl;
    }
    return 0;
}

发表于 2020-08-01 13:09:13 回复(0)
//试了O(n)的暴力破解,只过了35%就超时了,还是老老实实DFS吧哈哈,暴力的代码也贴在后面了
//DFS因为只考虑最优的路径。没想到递归调用的运行栈切换开销居然不是很大???
//DFS-----------------------------------------------
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
bool DFS(int* A, int n, vector<int>& record, int* curr, int last, int sum) {
    if (*curr == sum) return true;
    for (int i = 0; i < n; ++i) {
        if (last != i && A[i]) {
            if (A[i] > (sum - (*curr) + 1) / 2) {
                int tmp = record[--(*curr)];
                ++A[tmp - 1];
                record.pop_back();
                return false;
            }
            else {
                record.push_back(i + 1);
                last = i;
                --A[i];
                ++(*curr);
            }
            DFS(A, n, record, curr, last, sum);
        }
    }
    if (*curr == sum) return true;
    return false;
}
void print(int* A, int n, vector<int>& record, int* curr, int last, int sum) {
    if (A == nullptr || n < 1) printf("-");
    if (DFS(A, n, record, curr, last, sum)) {
        for (int i = 0; i < sum; ++i) {
            printf("%d ", record[i]);
        }
    }
    else printf("-");
}
int main() {
    int n;
    scanf("%d", &n);
    int* A = new int[n];
    int sum = 0;
    for (int i = 0; i < n; ++i) { scanf("%d", &A[i]); sum += A[i]; }
    vector<int> record;
    int x = 0;
    int* curr = &x;
    int last = -1;
    print(A, n, record, curr, last, sum);
    return 0;
}


//暴力---------------------------------------------------
#include<iostream>
#include<stdio.h>
using namespace std;
void print_seq(int* A, int n) {
    if (A == nullptr || n <= 0) { printf("-"); return; }
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += A[i];
    }
    for (int i = 0; i < n; ++i) {
        if ((sum + 1) / 2 < A[i]) { printf("-"); return; }
    }
    int curr = 0;
    int curr_1 = curr;
    ++curr;
    int curr_2;
    int last = -1;
    if (n > 1) { curr_2 = curr; ++curr; }
    else {
        if (sum == 1) {
            printf("%d", curr_1 + 1);
        }
    }
    for (int i = 0; i < sum; ++i) {
        if (last != curr_1 && A[curr_1] > 0) { last = curr_1; printf("%d ", curr_1 + 1); --A[curr_1]; }
        else if (last != curr_2 && A[curr_2] > 0) { last = curr_2; printf("%d ", curr_2 + 1); --A[curr_2]; }
        else {
            if (A[curr_1] == 0 && curr < n) {
                curr_1 = curr;
                ++curr;
            }
            if (A[curr_2] == 0 && curr < n) {
                curr_2 = curr;
                ++curr;
            }
            --i;
        }
    }
}
int main() {
    int n;
    scanf("%d", &n);
    int* A = new int[n];
    for (int i = 0; i < n; ++i) scanf("%d", &A[i]);
    print_seq(A, n);
    return 0;
}

发表于 2020-06-07 01:18:26 回复(0)
为啥同样的算法C++可以通过,python通不过
N=int(input())
a=[int(i) for i in input().split()]
m=sum(a)
if max(a)-(sum(a)-max(a))>2:
    print('-')
else:
 def add(a,left,out):
    if len(out)<m:
        for i in range(1,N+1):
           if i!=left and a[i-1]>0:               
             a[i-1]=a[i-1]-1
             if max(a)-(sum(a)-max(a))<2:
               out.append(i)   
               add(a,i,out)  
             else:
               a[i-1]=a[i-1]+1
               dex=a.index(max(a))
               a[dex]=a[dex]-1
               out.append(dex+1)
               add(a,dex+1,out)              

 out=[]
 add(a,-1,out)
 o=[]       
 for i in out:
  o.append(str(i))        
 print(' '.join(o)) 


编辑于 2020-04-18 11:20:33 回复(1)
#include <iostream>
#include <vector>
#include <utility>

using namespace std;

pair<bool,vector<int>> solution( const vector<int> &trees, int current, int ntrees ) {
	if (ntrees == 0)
		return make_pair(true, vector<int>());

	for (int i = 0; i < trees.size(); ++i) {
                // 剪枝,任意树的数量大于总数目的一般,肯定不能交替种树
		if( trees[i] > (ntrees+1) /2 ) 
			return make_pair(false, vector<int>());

		if (i != current && trees[i] > 0 ) {
			vector<int> remain(trees);
			--remain[i];
			pair<int,vector<int>> tmp = solution(remain, i, ntrees-1);
			if (tmp.first) {
				tmp.second.push_back(i+1);
				return tmp;
			}
		}
	}

	return make_pair(false, vector<int>() ) ;
}

int main() {
	int N;
	while (cin >> N)
		break;

	int tmp;
	int ntrees = 0;
	vector<int> trees(N,0); 
	for (int i = 0; i < N; ++i) {
		cin >> trees[i];
		ntrees += trees[i];
	}
	
	pair<bool,vector<int>> ret = solution(trees, -1, ntrees );
	
	if (ret.first) {
		for (auto iter = ret.second.rbegin(); iter != ret.second.rend(); ++iter)
			cout << *iter << " ";
		cout << endl;
	}
	else
		cout << "-" << endl;

	return 0;
}

编辑于 2020-04-10 14:38:53 回复(0)
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("-");
        }
    }
}

发表于 2020-04-09 19:03:59 回复(0)
之前一直没有看懂高赞答案中,进行回溯的两行代码。现在终于理解了,见我的注释
for (int i = 1; i <= n; i++) {//每次从第一种树开始进行dfs尝试
                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);//回溯的原因:情况1:如三种树数量为{4,2,1},则结果为1,2,1,2,1,3,1,不用回溯
                    // 情况2:如另外三种树{1,2,4},按照字典序顺序尝试的话,最开始是1,2,3,2,3,3,显然不满足,所以应该回退、回退,直到3,1,3,2,3,2,3
                    tree[i]++;
                }
            }


编辑于 2020-03-22 20:26:00 回复(0)