读题

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

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

例如:

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

#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代码

#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;
}

标题:P1120 小木棍
作者:shiquda
地址:https://shiquda.link/P1120
除非特别说明,本博客上的所有内容均在CC BY-SA 4.0许可下提供。 如需转载请注明作者与来源,谢谢!