蓝桥算法训练粘木棍（C++）

问题描述

　　有N根木棍，需要将其粘贴成M个长木棍，使得最长的和最短的的差距最小。

输入格式

　　第一行两个整数N,M。
　　一行N个整数，表示木棍的长度。

输出格式

　　一行一个整数，表示最小的差距

样例输入

3 2
10 20 40

样例输出

数据规模和约定

　　N, M<=7

题目链接：“蓝桥杯”练习系统

思路一：

此题给出的知识标签是搜索，那就想dfs，不断尝试两个数据合并一个数据，当到达m个数据时，寻找此时最大最小值，做差，然后回溯，换两个数据合并，到达m个数，再回溯…… 直到所有情况合并完，对于这个题来说，n,m都小于等于7，这样做完全没问题，但是时间复杂度比较大，盲目搜索，有一些不必要的合并，这种方法不太推荐，写一下代码，交上也可以过。

#include<iostream>
using namespace std;
int n,m;
int a[10];
int sum=0x3f3f;
void dfs(int k) {
	if(k==m) {
		int maxx=0;
		int minx=0x3f3f;
		for(int i=0; i<m; i++) {
			minx=min(minx,a[i]);
			maxx=max(maxx,a[i]);
		}
		sum=min(maxx-minx,sum);
		return;
	}
	for(int i=0; i<k; i++) {
		for(int j=i+1; j<k; j++) {
			a[i]+=a[j];
			int tmp=a[j];
			a[j]=a[k-1];
			a[k-1]=tmp;
			dfs(k-1);
			tmp=a[j];
			a[j]=a[k-1];
			a[k-1]=tmp;
			a[i]-=a[j];
		}
	}
}
int main() {
	cin>>n>>m;
	for(int i=0; i<n; i++) {
		cin>>a[i];
	}
	dfs(n);
	cout<<sum<<endl;
	return 0;
}

思路二：

思路二就有点贪心的思想了，我们可以简化为一个模型，有n个数，m个箱子，不断往里面放数，每放一个数就要遍历一遍寻找最小值的箱子，然后把数放进去，直到放完为止，越往后的数，数越小（前提由大到小排好序），这样也就达到了我们寻找最小差值的目的。首先我们先初始化m个箱子的初始值，我们要选n个数中前m大的数，作为m个箱子的初始值，为什么选前m大的值，因为我们要求最小差值，先放完最大值，剩下小的，不断往里面补，使得减小差值的目的，比如样例，10 20 40，先选，20，40作为箱子，遍历一遍寻找最小值20，把10放进去，更新为30，数都放完了，此时最小差值10。如果前m小的数作为箱子，10，20，寻找最小值10，把40放进去，更新为50，最小差值为20。这样保证了每次更新都是有用的更新，大大降低了时间复杂度。话不多说，上代码。

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int a[10],b[10];
int cmd(int A,int B){
	return A>B;
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n,cmd);//由大到小排序
	for(int i=m;i<n;i++){//遍历除去前m大的数，往里面添加
		int index=0;
		int minx=0x3f3f3f;
		for(int j=0;j<m;j++){//选取前m大的数相当于箱子，哪个数小，就往里放
			if(a[j]<minx){//寻找此时前m大的数最小值
				index=j；//记录下标
				minx=a[j];//更新值
			}
		}
		a[index]+=a[i];//找到最小的值（箱子），把此时未放进去的数，加上
	}
	int maxx=0;
	int minx=0x3f3f3f;
	for(int i=0;i<m;i++){//寻找此时最大最小值，做差
		maxx=max(maxx,a[i]);
		minx=min(minx,a[i]);
	}
	cout<<maxx-minx<<endl;
	return 0;
}