问题描述
有N根木棍，需要将其粘贴成M个长木棍，使得最长的和最短的的差距最小。
输入格式
第一行两个整数N,M。 一行N个整数，表示木棍的长度。
输出格式
一行一个整数，表示最小的差距
样例输入
3 2 10 20 40
样例输出
10
数据规模和约定
N, M<=7
题目链接：“蓝桥杯”练习系统
思路一：
此题给出的知识标签是搜索，那就想dfs，不断尝试两个数据合并一个数据，当到达m个数据时，寻找此时最大最小值，做差，然后回溯，换两个数据合并，到达m个数，再回溯…… 直到所有情况合并完，对于这个题来说，n,m都小于等于7，这样做完全没问题，但是时间复杂度比较大，盲目搜索，有一些不必要的合并，这种方法不太推荐，写一下代码，交上也可以过。
代码语言：javascript复制#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。这样保证了每次更新都是有用的更新，大大降低了时间复杂度。话不多说，上代码。
代码语言：javascript复制#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;
}
以上为本人刷题思路总结，此题比较简单，属于小白签到题，愿与大家共同进步。
