洛谷P1489题解：动态规划解决分队问题

一、问题分析

题目要求将n个人分成两队，使得两队总血量尽可能接近，同时两队人数也要尽可能平衡。这是一个典型的分组优化问题，可以使用动态规划高效解决。

二、算法核心思路

1. 动态规划定义：

• dp[i][j]表示选i个人能否组成j血量

• 采用三维降维优化，节省空间复杂度

2. 状态转移：

• 逆序更新避免重复计算

• 三重循环分别处理：人员、人数、血量

3. 最优解搜索：

• 寻找最接近总血量一半的组合

• 同时考虑人数平衡的优化

三、完整代码实现（带注释）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);  // 加速输入输出
    cin.tie(nullptr);             // 解除cin与cout的绑定
    
    int n;
    cin >> n;
    vector<int> blood(n);
    int total = 0;
    
    for (int i = 0; i < n; ++i) {
        cin >> blood[i];
        total += blood[i];
    }

    // dp[i][j]表示选i个人能否组成j血量
    vector<vector<bool>> dp(n/2+2, vector<bool>(total/2+1, false));
    dp[0][0] = true;  // 初始状态：0个人0血量

    for (int k = 0; k < n; ++k) {
        for (int i = min(k, n/2); i >= 0; --i) {
            for (int j = total/2; j >= blood[k]; --j) {
                if (dp[i][j-blood[k]]) {
                    dp[i+1][j] = true;
                }
            }
        }
    }

    // 寻找最优解：最接近total/2且人数最平衡
    int best_sum = 0, best_count = 0;
    for (int j = total/2; j >= 0; --j) {
        for (int i = 0; i <= n/2; ++i) {
            if (dp[i][j]) {
                if (abs(total-2*j) < abs(total-2*best_sum)) {
                    best_sum = j;
                    best_count = i;
                } else if (abs(total-2*j) == abs(total-2*best_sum)) {
                    if (abs(n-2*i) < abs(n-2*best_count)) {
                        best_count = i;
                    }
                }
            }
        }
    }

    cout << min(best_sum, total-best_sum) << " " 
         << max(best_sum, total-best_sum) << endl;
    return 0;
}

四、调试技巧

1. 使用小规模测试数据验证

2. 打印中间状态检查

3. 验证边界条件

4. 检查状态转移是否正确