题解：UVA10482 The Candyman Can

~~这题是橙题，它配吗？~~

题意

将

n

个数的数列分为

3

组，使总和最大的一组与总和和最小的一组的差最小。

思路

本体算法：动态规划。

建一个二维数组，用 dp 枚举

3

组里数的和，知道两组的和，使用减法算出第三组和。

使用

f_{i, j}

表示第一组和为

i

，第二组和为

j

，能否构造出来。

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

注意

直接枚举一个数有可能被算

2

次，要将新的可行状态标记为

−1

，每执行完上面这一段代码后将其变为

1

即可。

代码

CPP

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

题解：UVA10482 The Candyman Can

文章操作

题意

思路

注意

代码

相关推荐

评论

题解：UVA10482 The Candyman Can