蓝桥杯——粘木棍 (C++)

题目来源：蓝桥杯算法训练

知识点：DFS搜索

问题描述
　　有N根木棍，需要将其粘贴成M个长木棍，使得最长的和最短的的差距最小。
输入格式
　　第一行两个整数N,M。
　　一行N个整数，表示木棍的长度。
输出格式
　　一行一个整数，表示最小的差距
样例输入
3 2
10 20 40
样例输出
10
数据规模和约定
　　N, M<=7

题目分析

暴力法 思路：列举所有可能的组合，比较求最小差距。显然这种做法在计算过程中包含大量的重复计算，耗时较长。

采用 DFS+穷举 的思路：每次选择两根木棍进行合并，新木棍加入数组，两个旧的舍去。n根木棍要合并成m根，相当于需要合并n - m次，即舍去n - m根旧的。

如何舍去旧木棍，加入新木棍呢？可以使用两层for循环遍历，取出两根木棍，将合并的新长度放入其中一个旧木棍在数组中的位置，将另一个旧木棍的位置与最后n-1的位置交换。在使用 DFS 进行搜索时，参数为当前数组长度，往下搜索时长度递减即可。

代码

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

#define MAX 9999
#define MIN -9999

const int maxn = 10;
int lens[maxn];
int n, m, d; 

void DFS(int k) {
	if(k == m) {
		int maxL = MIN;
		int minL = MAX;
		for(int i=0; i<k; i++) {
			if(lens[i] < minL) minL = lens[i];
			if(lens[i] > maxL) maxL = lens[i];
		}
		d = min(d, maxL - minL);
		return;
	}
	
	for(int i=0; i<k; i++) {
		for(int j=i+1; j<k; j++) {
			lens[i] += lens[j];
			swap(lens[j], lens[k-1]);
			DFS(k-1);
			swap(lens[j], lens[k-1]);
			lens[i] -= lens[j];
		}
	}
}

int main() {
	cin >> n >> m;
	for(int i=0; i<n; i++) {
		cin >> lens[i];
	}
	
	d = MAX;
	DFS(n);
	cout << d << endl;
	
	return 0;
}

注意：

• 进行DFS 时，当数组长度k等于m，说明已经完成分组。此时找出数组中的最大值与最小值，但不能对数组进行排序，因为会打乱数组顺序。
• 完成 DFS 回到上一步时，要恢复合并之前的两根木棍的长度和位置。