Sticks

博主： admin
发布时间：2021 年 02 月 22 日
430次浏览
暂无评论
2357字数
分类：蓝桥杯

# Sticks

## 题目

**资源限制**

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

**问题描述**

George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.

**输入格式**

The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.

**输出格式**

The output should contains the smallest possible length of original sticks, one per line.

**样例输入**

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

**样例输出**

6
5

## 题目翻译

将所给的木棍拼接成若干个长度相等的木棒，求木棒的最短长度。

## 题目分析

* 木棒的长度最短是木棍长度的最大值；最长是木棍的总长度
* 木棒长度能整除木棍总长度
* 如果一开始就使用短的木棍组成了一根木棒，那么这根木棒可能不对，将来还要回溯(`可能当前木棒中的若干木棍可以由一个未使用的稍长木棍代替，而短木棍会被用来组成其他木棒`)。例如木棍长度为：8，2，18，12，10，10。木棒长度为20时进行搜索，第一轮搜索搜到了8，2，10，显然需要回溯。然而将木棍按照长度从大到小排序后(18，12，10，10，8，2)，可以确保无需回溯，这是因为从大到小排序后如果选中了一根木棍使得后续可以组成一根木棒后，尽可放心寻求组成下一根木棒。`本题的精髓就是将木棍从大到小排序。`
* 此外还需要剪枝以缩短运行时间
  * 当前木棒长度为0时，如果使用最长的未使用的木棍后不可行，那么这跟木棍始终不会用上(`后面的木棒可选木棍是当前可选木棍的子集`)，因此所给木棍不能拼接成若干个长度相等的木棒
  * 如果使用了一根木棍使得当前木棒长度达到所需长度后，剩余未使用的木棍不能拼接成若干所需长度的木棒，那么会拼接失败
  * 不使用当前木棍时，需要跳过其后与其长度相等的木棍以节省时间

## C++代码

```cpp
#include<iostream>
#include<algorithm>
using namespace std;

int length; //木棒长度
bool used[64]; //记录各个木棍是否使用过
int s[64]; //木棍长度
int max_length; //木棒的最长长度
int n; //木棍个数

//从大到小排序
bool cmp(int a, int b) {
	return a > b;
}

//深度优先搜索
//finished:已完成的木棒根数
//cur_length:当前木棒已拼接的长度
//start:从哪根木棍开始
bool dfs(int finished, int cur_length, int start) {
	//测试是否完成
	if (finished * length == max_length)
		return true;

//当前木棒拼接完成
	if (cur_length == length)
		return dfs(finished + 1, 0, 0);

for (int i = start; i < n; ++i) {
		if (used[i])
			continue;
		int l = s[i];

//测试当前木棍
		if (cur_length + l <= length) {

//若使用当前木棍后，剩余的木棍可以完成任务则可以完成任务
			used[i] = true;
			if (dfs(finished, cur_length + l, i + 1))
				return true;

//使用当前木棍后，剩余木棍不可以完成任务，则不使用当前木棍
			used[i] = false;

//剪枝:若当前木棍本该是组成木棒的第一根或最后一根，则失败
			if (cur_length == 0 || cur_length + l == length)
				return false;

//剪枝:跳过相同长度的木棍
			int j = i;
			while (j < n && s[j] == l)++j;
			i = j - 1;
		}
	}
	return false;
}

int main() {
	cin >> n;
	while (n) {
		max_length = 0;
		length = 0;
		for (int i = 0; i < n; ++i) {
			used[i] = false;
			cin >> s[i];
			max_length += s[i];
			if (s[i] > length)length = s[i];
		}
		sort(s, s + n, cmp);
		while (length <= max_length) {
			if (max_length % length == 0 && dfs(0, 0, 0)) {
				cout << length << endl;
				break;
			}
			++length;
		}
		cin >> n;
	}
	return 0;
}
```

最后修改：2021 年 02 月 26 日 03 : 02 PM

如果觉得我的文章对你有用，请随意赞赏