Skip to content

洛谷 - P1120 小木棍

题解约 1.1 千字
检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过 5050

现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。

给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。

#输入格式

第一行是一个整数 nn,表示小木棍的个数。 第二行有 nn 个整数,表示各个木棍的长度 aia_i

#输出格式

输出一行一个整数表示答案。

#输入输出样例

样例输入 #1

9
5 2 1 5 2 1 5 2 1

样例输出 #1

6

#数据范围与提示

对于 100%100\% 的测试点,1n651 \leq n \leq 651ai501 \leq a_i \leq 50

#思路

搜索,大力剪枝。

提示:请区分好下文中「长棍」和「木棍」的区别,前者指拼接出的成品木棍,后者指题目中提供的被砍断的小木棍。
  1. 显然,一根长木棍的灵活性一定比一根短木棍要小,那么需要先尽可能地使用掉长木棍,再使用短木棍填补空缺。

    void dfs(int, int, int) 中:
    23
    24
    25
    26
    27
    28
    29
    30
    31
    for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
    vis[i] = true;
    dfs(now + 1, i, l - a[i]);
    vis[i] = false;

    break;
    }
    }
    void dfs(int, int, int) 中:
    36
    37
    38
    39
    for (int i = p; i <= n; i++) {
    if (!vis[i]) {
    vis[i] = true;
    dfs(now, i, rest - a[i]);
    int main() 中:
    66
    67
    68
    69
    70
    71
    for (l = a[1]; l <= sum / 2; l++) {
    if (sum % l) continue;

    m = sum / l;
    dfs(1, 1, l - a[1]);
    }

    优先使用未使用的木棍中最长的那根。

  2. 当第一根长度为 xx 的木棍拼接失败之后就不能再使用其他相同长度的木棍了,直接跳到下一个长度即可。

    void dfs(int, int, int) 中:
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    for (int i = p; i <= n; i++) {
    if (!vis[i]) {
    vis[i] = true;
    dfs(now, i, rest - a[i]);
    vis[i] = false;

    if (rest == a[i]) return;
    i = next[i];
    }
    }
  3. 由于原始长度是从小到大枚举的,所以第一次搜索到的答案就是最小长度,直接输出答案并结束程序即可。

  4. 如果当前长棍剩余的未拼长度等于当前木棍的长度,继续拼下去时却失败了,就直接回溯不再继续。

    void dfs(int, int, int) 中:
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    for (int i = p; i <= n; i++) {
    if (!vis[i]) {
    vis[i] = true;
    dfs(now, i, rest - a[i]);
    vis[i] = false;

    if (rest == a[i]) return;
    i = next[i];
    }
    }

    当前长棍剩余的未拼长度等于当前木棍的长度时,显然这根木棍拼到当前长棍上最优(短木棍留到后面插缝用)。如果在最优情况下继续拼下去还是失败了,那么之前肯定有木棍用错了,直接回溯即可。

  5. 只选择长度不大于未拼长度 rest\mathit{rest} 的木棍继续拼接,原因显然。

    void dfs(int, int, int) 中:
    33
    34
    35
    36
    37
    38
    39
    // 二分查找第一个长度 <= rest 的木棍所在的位置
    int p = std::lower_bound(a + last + 1, a + n + 1, rest, std::greater<int>()) - a;

    for (int i = p; i <= n; i++) {
    if (!vis[i]) {
    vis[i] = true;
    dfs(now, i, rest - a[i]);

#代码

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
#include <iostream>
#include <algorithm>
#include <functional>
#include <numeric>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 70;

int n, m, l, a[N], next[N];
bool vis[N]{false, true};

void dfs(int now, int last, int rest) {
if (!rest) {
if (now == m) {
cout << l << endl;

exit(0);
}

for (int i = 1; i <= n; i++) {
if (!vis[i]) {
vis[i] = true;
dfs(now + 1, i, l - a[i]);
vis[i] = false;

break;
}
}
}

int p = std::lower_bound(a + last + 1, a + n + 1, rest, std::greater<int>()) - a;

for (int i = p; i <= n; i++) {
if (!vis[i]) {
vis[i] = true;
dfs(now, i, rest - a[i]);
vis[i] = false;

if (rest == a[i]) return;
i = next[i];
}
}
}

int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n;

for (int i = 1; i <= n; i++) {
cin >> a[i];
}

int sum = std::accumulate(a + 1, a + 1 + n, 0);

std::sort(a + 1, a + 1 + n, std::greater<int>());

for (int i = n; i; i--) {
next[i] = a[i] == a[i + 1] ? next[i + 1] : i;
}

for (l = a[1]; l <= sum / 2; l++) {
if (sum % l) continue; // 不能拼出整数根长棍时就跳过

m = sum / l;
dfs(1, 1, l - a[1]);
}

cout << sum << endl;

return 0;
}