题解：UVA10482 The Candyman Can

furina_yyds · 2025-01-14 11:06:11 · 题解

这题是橙题，它配吗？

题意

将 n 个数的数列分为 3 组，使总和最大的一组与总和和最小的一组的差最小。

思路

本体算法：动态规划。

建一个二维数组，用 dp 枚举 3 组里数的和，知道两组的和，使用减法算出第三组和。

使用 f_{i, j} 表示第一组和为 i，第二组和为 j，能否构造出来。

最后枚举每种存在的状态，直接求即可。

注意

直接枚举一个数有可能被算 2 次，要将新的可行状态标记为 −1，每执行完上面这一段代码后将其变为 1 即可。

代码

#include <iostream>
#include <algorithm>
#include <cstring>

// 将 int 定义为 long long 以处理更大范围的整数
#define int long long

// 处理测试用例的函数
void solve() {
    // 元素数量
    int n;
    std::cin >> n;
    // 存储元素的数组
    int a[n + 1];
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
        sum += a[i];
    }
    // 动态规划数组，dp[j][k] 表示某种状态
    bool dp[1010][1010] = {false};
    dp[0][0] = true;
    for (int i = 1; i <= n; ++i) {
        for (int j = sum; j >= a[i]; --j) {
            for (int k = 0; k <= sum; ++k) {
                if (dp[j - a[i]][k] || dp[k][j - a[i]]) {
                    dp[j][k] = true;
                }
            }
        }
    }
    int min_diff = 1e18;
    for (int i = 0; i <= sum; ++i) {
        for (int j = 0; j <= sum; ++j) {
            if (dp[i][j]) {
                int third = sum - i - j;
                int max_val = std::max({i, j, third});
                int min_val = std::min({i, j, third});
                min_diff = std::min(min_diff, max_val - min_val);
            }
        }
    }
    std::cout << min_diff << "\n";
}

int main() {
    // 测试用例数量
    int T;
    std::cin >> T;
    for (int case_num = 1; case_num <= T; ++case_num) {
        std::cout << "Case " << case_num << ": ";
        solve();
    }
    return 0;
}