小多想在美化一下自己的庄园。他的庄园毗邻一条小河，他希望在河边种一排树，共 M 棵。小多采购了 N 个品种的树，每个品种的数量是 Ai (树的总数量恰好为 M)。但是他希望任意两棵相邻的树不是同一品种的。小多请你帮忙设计一种满足要求的种树方案。
[编程题]种树
- 热度指数：8078 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
第一行包含一个正整数 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)
/*
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)
深搜求解，注意当一种树的总数超过剩余树的一半时，肯定没法完成所有相邻的树品种都不同，利用这个条件进行剪枝。
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
回复(2)
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)
思路：
使用搜索来做，但纯粹使用搜索的话通过率为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)
#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)
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1005;
const int M = 2005;
bool flag = false;
int n, a[N], sum, ans[M];
void dfs(int cnt, int x){
if(flag) return;
if(cnt > sum){
flag = true;
for(int i = 1; i <= sum; ++i) cout << ans[i] << " ";
cout << endl;
return;
}
int res = sum - cnt + 1;
for(int i = 1; i <= n; ++i){
if(a[i] > (res + 1) / 2){
return;
}
}
for(int i = 1; i <= n; ++i){
if(i == x) continue;
if(a[i] > 0){
a[i]--;
ans[cnt] = i;
dfs(cnt + 1, i);
ans[cnt] = 0;
a[i]++;
}
}
}
signed main(){
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> a[i];
sum += a[i];
}
dfs(1, 0);
if(!flag) cout << "-" << endl;
}
发表于 2024-04-11 23:48:34
回复(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;
}
//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;
}
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))
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)
问题信息
通过挑战的用户
查看代码-
2023-03-11 16:14:07
-
2023-03-07 15:07:50
-
2022-09-03 12:18:54 -
2022-09-03 11:26:51
-
2022-08-26 11:08:47
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
