蓝桥杯练习试题：试题 算法训练 粘木棍

资源限制

时间限制：1.0s   内存限制：256.0MB

问题描述

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

输入格式

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

输出格式

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

样例输入

3 2
10 20 40

样例输出

10

数据规模和约定

N, M<=7

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10;
int n, m, a[N], d[N];
int temp = 9999999;
bool st[N];
void dfs(int u)
{
	if(u == n)       //如果已经走到最后则算出最小值 
	{
		int s1 = d[0], s2 = d[0];
		for(int i = 0; i < m; i ++ )
		{
			s1 = max(s1, d[i]);
			s2 = min(s2, d[i]);
		}
		temp = min(temp, s1 - s2);
		return ;
	}
	
	for(int i = u; i < n; i ++ )      //从u个元素开始枚举
	{
		for(int j = 0; j < m; j ++ )  //满足有m种情况时退出 
		{
			if(!st[i])                //i没有出现过 
			{
				d[j] += a[i];
				st[i] = true;
				dfs(u + 1);
				d[j] -= a[i];         //回溯 
				st[i] = false;
			}
		}
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
	dfs(0);
	printf("%d", temp);
	return 0;
}