一、题目解读洛谷P1489题要求将n个人的血量分配为两组,使两组血量之差最小,同时人数尽可能平衡。这是一类典型的组合优化问题,需要高效算法找到**解。题目难点在于如何在有限时间内计算所有可能的组合,并从中筛选出**结果。 二、解题思路采用动态规划(Dynamic Programming)解决该问题。核心思想是将原问题分解为子问题,利用子问题的**解推导整体**解。通过构建二维dp数组dp[j]表示“选i个人能否组成j血量”,逐步迭代求解,最终找到最接近总血量一半的分配方案,并兼顾人数平衡。 三、解题步骤1. 数据预处理:输入n和每个人的血量,计算总血量total,初始化dp数组。 2. 动态规划迭代:外层循环遍历人数k,内层双循环倒序枚举人数i和血量j,利用状态转移方程dp[i+1][j] = dp[j-blood[k]]更新。 3. **解筛选:从dp数组中寻找最接近total/2的血量值,同时比较人数差,优先选择人数更平衡的方案。 4. 输出结果:输出两组血量的最小值和**值。 四、代码与注释
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr); // 加快输入输出速度
- 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
- 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;
- }
复制代码
五、总结本文通过动态规划方法解决了洛谷P1489的血量分配问题,核心在于将复杂组合问题转化为状态转移方程,并通过优化迭代过程降低时间复杂度。代码中通过倒序循环避免重复计算,**解筛选兼顾了血量差和人数平衡的双重要求,为同类背包问题提供了高效参考方案。
|