本题的基本解法是使用深度优先搜索算法,仍然是入门难度,但比其他的问题稍稍困难一点的地方在于需要针对性地剪枝,非常经典,值得深入研究。
有一些长度相等的木棍,把它们随机切开,会得到另外一组木棍。已知切削后的木棍长度,求可能的最小原有木棍长度。本题中原有木棍和切削后木棍的长度均保证为整数。
本题会有多次输入数据测试,多次输入以换行作为分隔。每次输入有两个部分组成,以换行符分隔为两行:第一行的整数标明第二行数据的个数;第二行的多个整数以空格分隔,表示切削后的木棍长度。示例输入为:
1
2
3
4
5
| 9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
|
对每组输入数据,输出最小原有木棍长度。实例输出为:
深度优先搜索是图论算法中最基本也是最重要的算法之一,和广度优先搜素一起组成树的常用搜索算法。本算法要求尽可能的深地搜索树的分支,如果对应节点的所在边都己被搜索过,搜索将回溯到发现这个节点的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止,属于盲目搜索。
实现方法为:
- 构造辅助数组以记录节点访问状态
- 从根节点出发开始搜索
- 如果当前搜索路径符合要求则搜索成功,退出搜索程序
- 搜索当前节点的子节点:如果未访问则计入搜索路径,而且更改节点状态为已访问;否则,跳过这个子节点,直到找到一个为访问过的子节点
- 如果存在步骤 3 中要求的子节点,则再从这个子节点开始新的搜索
- 如果不存在步骤 3 中要求的子节点,则表示当前搜索路径已达到尽头,应该回溯到上一个搜索启动节点,即上上一个搜索启动节点的下一个子节点,同时为了保证其他搜索路径不出错,将当前启动节点状态记为未访问
- 不断重复 3 到 6 的步骤,直到搜索完全部节点,如果还没有答案则表示带搜索的目标不存在
一般深度优先搜索都使用递归方法描述,用 Java 格式的伪代码表示为:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| /**
* DFS核心伪代码
* 前置条件是visit数组全部设置成false
* @param n 当前开始搜索的节点
* @param d 当前到达的深度,也即是路径长度
* @return 是否有解
*/
bool DFS(Node n, int d){
if (d == TARGET){//路径长度为目标长度则返回true,表示此次搜索有解
return true;
}
for (Node nextNode in n){//遍历跟节点n相邻的节点nextNode,
if (!visit[nextNode]){//未访问过的节点才能继续搜索
//例如搜索到节点V1了,那么节点V1要设置成已访问
visit[nextNode] = true;
//接下来要从V1开始继续访问了,路径长度当然要加1
if (DFS(nextNode, d+1)){//如果搜索出有解
//例如到了节点V6,找到解了,你必须一层一层递归的告诉上层已经找到解
return true;
}
//重新设置成未访问,因为它有可能出现在下一次搜索的别的路径中
visit[nextNode] = false;
}
//到这里,发现本次搜索还没找到解,那就要从当前节点的下一个节点开始搜索。
}
return false;//本次搜索无解
}
|
剪枝是 ACM 解题方法中常用到的技巧,经常用来减少搜索等暴力算法的运算时间。剪枝的比喻很能说明问题,就是在数型数据结构的搜索中去掉无意义枝杈的搜索,以加速程序的运行。
一般来说,剪枝的逻辑和每个题目息息相关,题目之间各有不同,需要根据题目分析判断在哪里剪枝才能加速程序。一般要注意,题目中给出的数据范围、数据相互直接的逻辑关联,以及自己能够推导出的联系或公式。
本题看似给出的条件不多,实际是因为有暗含的条件需要解题者自己推理:
- 原来的长度必定可以整除所有木棍长度的和
- 原来的长度必定不小于输入数据中的最大值
这样我们可以先把所有木棍长度求和记为 sum
,同时确定木棍长度最大值,从最大值开始,实验 sum
的因子,直到 sum
本身找出符合题目要求的数。
对于每一个确定的因子,假设它是符合要求的长度,那么就可以使用现有的木棍拼接成长度等于因子的多个木棍。关键在于怎么拼接木棍。
实际上,我们应该降序排列木棍的长度,从最长的木棍开始拼接,因为相对来说短的木棍可以适应更多可能的拼接情况即“更灵活”,长木棍拼接法相对较少更易处理。
这样对于给定的长度 len
、木棍总长度 total
有拼接好的木棍数量 num = total / len
拼接办法有:
- 取出未使用的最长木棍,用
len
减去取出的木棍长度 - 从大到小搜索,保证拼接后的木棍不大于
len
:长度相等即拼接成功则拼接数 n 加一,重新开始步骤 1;小于 len
则继续搜索可能的木棍,将已拼接好的长度累加,重新开始步骤 2 - 不断重复 1 和 2,并把所有使用的木棍记上标记,直到拼好的木棍数量为
num
,表明 len
是合法的长度 - 如果检查了所有的拼接方案,都不能拼接出
num
个长度为 len
的木棍,则说明这个长度不符合要求
乍一看,数据动态变化很大,相互之间关系不好分辨,很难明白使用什么样的数据结构来组织数据。实际上,对于每个特定的 len
,可以拼接的长度范围是固定的,就是所选木棍长度不大于 len
减去已经拼接好的长度。而后,我们要依次拼接这些可行的木棍,并且不断重复这样的过程。对这样分层讨论,层层递进,并且有一对多的关系,可以考虑构造树形结构。
每个树形结构的节点都是拼接的木棍的长度,子节点为拼接方案的候选木棍长度,一旦拼接一根木棍成功,则子节点为下一次拼接的可以使用的最长木棍长度。如此,则题目的解就要求,构造的树高度为木棍的数目,且必须有一条根到叶子的路径包含所有木棍长度,而且符合拼接要求。
这样就能够确定题目解法应该为深度优先搜索。
对于以下输入数据
1
2
| 9
8 3 8 15 2 11 4 8 1
|
有构造的树和正确的构造路径如下所示:构造路径为 15-3-2-11-8-1-8-8-4
,木棍长度为 20。
搜索中会遇到几种情况,可以直接跳出搜索过程,判定当前长度并非答案,比如:
- 当前最长的木棍匹配失败
- 当前拼接成功,但是剩下的无法拼接成功
- 剩余未使用木棍的长度和小于要拼接的长度
同时,要注意到,输入的数据中长度会重复,那么一个木棍匹配失败,和它等长的木棍也就没有必要搜索了。
使用基本的深度优先搜索构造的代码如下(注意:并非正确答案,仅仅是为了说明):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
/**
*
*/
public class Main {
private static int n;
private static int[] sticks = new int[64];
private static boolean[] used = new boolean[64];
private static int length;
private static int numOfSticks;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
while ((n = Integer.parseInt(reader.readLine())) != 0) {
int total = 0;
String tmp = reader.readLine();
int index = 0;
for (String str : tmp.split(" ")) {
int t = Integer.parseInt(str);
total += t;
sticks[index++] = t;
}
Arrays.sort(sticks, 0, n);
for (int i = sticks[n - 1]; i <= total; i++) {
if (total % i != 0) continue;
length = i;
numOfSticks = total / length;
if (search(0, n - 1, 0)) {
System.out.println(i);
break;
}
}
for (int i = 0; i < n; i++) {
used[i] = false;
}
}
}
private static boolean search(int currentLength, int nextStick, int numOfUsedStick) {
if (currentLength == length) {
currentLength = 0;
nextStick = n - 1;
numOfUsedStick++;
}
if (numOfUsedStick == numOfSticks) {
return true;
}
for (; nextStick >= 0; nextStick--) {
if (used[nextStick]) continue;
if (currentLength + sticks[nextStick] <= length) {
used[nextStick] = true;
if (search(currentLength + sticks[nextStick], nextStick - 1, numOfUsedStick)) {
return true;
}
used[nextStick] = false;
}
}
return false;
}
}
|
程序中的 search()
方法使用了基本的深度优先搜索,实际上可以得出正确的数值,但是效率较低,需要进一步优化。
可以 AC 的代码如下所示:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
/**
*
*/
public class Main {
private static int n;
private static int[] sticks = new int[64];
private static boolean[] used = new boolean[64];
private static int length;
private static int numOfSticks;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
while ((n = Integer.parseInt(reader.readLine())) != 0) {
int total = 0;
String tmp = reader.readLine();
int index = 0;
for (String str : tmp.split(" ")) {
int t = Integer.parseInt(str);
total += t;
sticks[index++] = t;
}
Arrays.sort(sticks, 0, n);
for (int i = sticks[n - 1]; i <= total; i++) {
if (total % i != 0) continue;
length = i;
numOfSticks = total / length;
if (search(0, n - 1, 0)) {
System.out.println(i);
break;
}
}
for (int i = 0; i < n; i++) {
used[i] = false;
}
}
}
private static boolean search(int currentLength, int nextStick, int numOfUsedStick) {
if (currentLength == length) {
currentLength = 0;
nextStick = n - 1;
numOfUsedStick++;
}
if (numOfUsedStick == numOfSticks) {
return true;
}
while (nextStick >= 0) {
if (!used[nextStick]) {
if (currentLength + sticks[nextStick] <= length) {
used[nextStick] = true;
if (search(currentLength + sticks[nextStick], nextStick - 1, numOfUsedStick)) {
return true;
}
// 本次搜索失败
used[nextStick] = false;
// 最长木棍匹配失败
if (currentLength == 0) break;
// 当前匹配成功,但是剩余的无法合成
if (currentLength + sticks[nextStick] == length) break;
}
// 如果本次匹配失败,忽略和它等长的木棍
int i = nextStick - 1;
while (i >= 0 && sticks[i] == sticks[nextStick]) i--;
nextStick = i;
// 剩余木棍长度和小于要求,则无需继续搜索
int sumOfLastSticks = 0;
for (; i >= 0; i--) {
if (!used[i]) sumOfLastSticks += sticks[i];
}
if (sumOfLastSticks < length - currentLength) break;
continue;
}
nextStick--;
}
return false;
}
}
|