2023年第十四届蓝桥杯C/C++ A组 F题 买瓜

试题 F：买瓜

对于每一个西瓜，会有三种状态：买，买一半，不买。

利用深度优先搜索得到的搜索树是一棵完全三叉树，最坏时间复杂度为 $O(n^3)$​。这样肯定会超时，于是我们需要采取相关的剪枝操作。

由于西瓜重量取一半时有可能出现小数，所以将目标重量和每个西瓜的重量都*2来规避小数的情况。

搜索前我们定义一个后缀和数组 suf，用来记录购买当前西瓜之后的所有西瓜所能达到的最大重量；同时将西瓜重量数组降序排列，这样可使剪枝效果达到最优。

搜索时我们记录三个状态，当前所在层数 pos，当前西瓜重量和 sum，当前切瓜次数 cnt，当满足条件：

• pos>=n：所有层都遍历完成
• cnt>=ans：当前切瓜次数已经大于之前切瓜次数的最小值
• sum>m：当前西瓜重量大于购买总重量
• sum+suf[pos]<m：当前位置之后所有西瓜被购买也无法达到购买总重量

就进行剪枝操作，最后输出运行结果。

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 30;

int n, m; // n：西瓜数量 m：西瓜购买重量
int weights[N]; // 重量数组
long suf[N + 1]; // 重量数组的后缀数组
int ans = INT8_MAX; // 将结果初始化为INT8_MAX

/**
 * 进行深度优先搜索
 *
 * @param pos 当前搜索层数
 * @param sum 当前西瓜重量和
 * @param cnt 当前切瓜次数
 */
void dfs(int pos, long sum, int cnt) {
    // 找到了一个结果
    if (sum == m) {
        ans = min(ans, cnt);
        return;
    }
    // 剪枝操作
    if (pos >= n || cnt >= ans || sum > m || sum + suf[pos] < m) return;
    // 对三种选择进行搜索
    dfs(pos + 1, sum + weights[pos], cnt);
    dfs(pos + 1, sum + weights[pos] / 2, cnt + 1);
    dfs(pos + 1, sum, cnt);
}

int main() {
    cin >> n >> m;
    m *= 2; // 总重量*2
    // 输入西瓜重量
    for (int i = 0; i < n; i++) {
        cin >> weights[i];
        weights[i] *= 2;
    }
    // 逆序排序
    sort(weights, weights + n, greater<int>());
    // 求重量后缀和
    for (int i = n - 1; i >= 0; i--) {
        suf[i] = suf[i + 1] + weights[i];
    }
    dfs(0, 0, 0);
    if (ans == INT8_MAX) {
        cout << -1;
    } else {
        cout << ans;
    }
    return 0;
}
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