P1120 小木棍

发表于 分类于 阅读次数： 本文字数： 4.2k 阅读时长 ≈ 5 分钟

读题

P1120 小木棍 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

给 $n$ 个小木棍的长度 $a_i$ ，满足$1 \leq a_{i} \leq 50$ , $n \leq 650$ ，它们之间可以任意拼接，现在要让它们拼接后的长度相同，求这个相同长度的最小值。

例如：

1
2
9
5 2 1 5 2 1 5 2 1

其中最小的长度是6，分别由3个 5 1 和一个2 2 2拼成。

题目说是搜索题。

思路

这题看起来简洁易懂，但是实际操作起来却比较繁琐，我最早不信邪，使用贪心来尝试，结果不行，还是只能老老实实去写搜索。

首先分析一下题目中隐藏的数学性质：最终相同长度的木棍的数量范围是确定的，从1~n，那么木棍长度的可能取值其实是有限的，可以容易得出：长度一定能被所有木棍长度之和sum整除，且这个长度一定 ≥ 木棍长度 $a_i$ 的最大值。

因此，我们可以把答案的可能取值都先求出来，然后从小到大依次尝试能否合成。

至于如何判断能否合成，我最早使用贪心的思路是：把合成木棍看作“填充”，刚好填满则算合成一根。每一次从最大能被填入剩余空间的木棍开始填入，如果能顺利填完当然就是可以满足条件了，直接结束，返回这个长度就是最小的；如果遇到所有剩余的木棍都无法填入就说明不行，继续尝试下一个最小长度。

但是这个贪心算法有漏洞，判断为无法填入的情况，有可能有别的解。

反例：3 4 7 8 18 20

贪心45分

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
#include <bits/stdc++.h>

using namespace std;

int fac[50]{0};
int fac_cnt = 0;
int max_num = 0;
int bucket[51]{0};  // 统计每个长度的个数
int n;
int sum = 0;

bool is_valid(int p)
{
    cout << p << endl;
    int bucket_copy[51]{0};
    for (int i = 0; i <= max_num; i++)
    {
        bucket_copy[i] = bucket[i];
    }

    for (int i = 0; i < sum / p; i++)
    {
        int max_num_copy = max_num;
        int pp = p;
        while (pp > 0)
        {
            if (bucket_copy[max_num_copy] == 0 ||
                max_num_copy > pp)  // 查找最低能被减的值
            {
                do
                {
                    if (max_num_copy == 0)
                    {
                        cout << "FAILED\n";
                        return false;
                    }
                    max_num_copy--;
                } while (bucket_copy[max_num_copy] == 0 || max_num_copy > pp);
            }
            pp -= max_num_copy;
            bucket_copy[max_num_copy]--;
            cout << max_num_copy << '\n';
        }
    }
    return true;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int ai;
        cin >> ai;
        max_num = max(ai, max_num);
        sum += ai;
        bucket[ai]++;
    }

    // 对sum求因子
    for (int i = max_num; i <= sum; i++)
    {
        if (sum % i == 0)  // 整除
        {
            fac[fac_cnt++] = i;
        }
    }

    for (int i = 0; i < fac_cnt - 1; i++)
    {
        if (is_valid(fac[i]))
        {
            cout << fac[i] << endl;
            system("pause");
            exit(0);
        }
    }
    cout << sum << endl;  // 都不满足则是sum

    system("pause");
    return 0;
}

于是我还是老老实实地写搜索了，搜索其实思路也不难，我这边用的是dfs。每次合成木棍，写一个循环从长到短选择合适的木棍填入，然后进入下一状态，如果所有长度的木棍都试了也不行，则返回false；如果所有的木棍都合成完毕才返回true。

难在如何对搜索进行剪枝优化。剪枝操作就是在某种状态下，已经能够确定结果是什么了，就停止“递”，马上“归”的操作。

先要明白一个结论：如果需要某个长度，比如说5，而此时你还有2、3，那么选择5可以看作是选择2、3的“上位”，因为2、3合起来完全可以替代5，而反过来就不行了。因此我们要优先选择5，后面再尝试2、3，这就是从大往小搜索的原因。

这里就写几个最关键的优化，至于其他无关痛痒的优化，😂👉🤡：

  1. 使用桶来装木棍的长度。桶的好处在于，既能按从长到短的顺序取出木棍，又能充当vis数组，“记录”已经访问的长度的信息。
  2. 每次查找可用木棍的时候，从上次查找到的地方继续，不用从头开始查找。因为如果填入比上次更长的木棍可以的话，就应该优先选，这样上次不应选小的木棍。
  3. 如果在剩下的长度和当前木棍的长度一样，但发现这根填进去返回false，直接跳出循环，判断这个分支为false，因为这已经是最优的选择了，如果选择用更小的木棍来补成这个长度肯定更不行。
  4. 如果一点都没填且发现失败了，也直接返回false，道理和上面一样，最优的填法都不能完成，更不用说更不好的了。

说实话3,4这两个优化挺难想的，没看大佬的题解基本想不出来，当时自己最优就拿了50来分。还得多向大佬学习。

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
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>

using namespace std;

int fac[50]{0};
int fac_cnt = 0;
int max_num = 0;
int min_num = 100;
int bucket[51]{0};  // 统计每个长度的个数
int n;
int sum = 0;
int current_fac;
int filled_bucket[50]{0};
int filled_bucket_cnt = 0;

bool dfs(int l, int x, int idx)
{
    // l是当次剩余的长度，x是次数，idx是上次搜到的索引
    if (l == 0)
    {
        if (x == 2)  // 剩一个一定可以拼
        {
            return true;
        }
        else
        {
            return dfs(current_fac, x - 1, 0);
        }
    }

    if (l < min_num)  // 剩下的比最小长度还小
    {
        return false;
    }

    for (int i = idx; i < filled_bucket_cnt; i++)
    {
        if (bucket[filled_bucket[i]] > 0)
        {
            bucket[filled_bucket[i]]--;
            if (dfs(l - filled_bucket[i], x, i))
            {
                // cout << i << '\n';
                bucket[filled_bucket[i]]++;
                return true;
            }
            else if (l == current_fac || l == filled_bucket[i])
            {
                bucket[filled_bucket[i]]++;
                return false;
            }

            bucket[filled_bucket[i]]++;
        }
    }
    return false;
}

bool cmp(int a, int b)
{
    return a > b;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int ai;
        cin >> ai;
        max_num = max(ai, max_num);
        min_num = min(ai, min_num);
        sum += ai;
        if (bucket[ai] == 0)
        {
            filled_bucket[filled_bucket_cnt++] = ai;
        }
        bucket[ai]++;
    }

    sort(filled_bucket, filled_bucket + filled_bucket_cnt, cmp);

    // 对sum求因子
    for (int i = max_num; i <= sum; i++)
    {
        if (sum % i == 0)  // 整除
        {
            fac[fac_cnt++] = i;
        }
    }

    for (int i = 0; i < fac_cnt - 1; i++)
    {
        current_fac = fac[i];
        if (dfs(fac[i], sum / fac[i], 0))
        {
            cout << fac[i] << endl;
            exit(0);
        }
    }
    cout << sum << endl;  // 前几个都不满足则是sum

    return 0;
}