P1599. Station Balance 题解

一、题目分析

本题要求将若干标本分配到有限的舱室中（每个舱室最多放2个标本），使得所有舱室质量与平均质量的绝对差之和（不平衡度）最小。核心在于找到一种分配方式，使得各舱室质量尽可能接近平均值。

二、解题思路

问题建模

• 约束条件：每个舱室可放0、1或2个标本，总标本数 ( S \leq 2C )（C为舱室数）。
• 目标函数：最小化 ( \text{IMBALANCE} = \sum |\text{CM}_i - \text{AM}| )，其中 ( \text{AM} ) 是总质量除以舱室数。

算法选择

由于舱室数 ( C \leq 5 )，标本数 ( S \leq 10 )，数据规模较小，可采用深度优先搜索（DFS）+ 回溯法暴力枚举所有可能的分配方案，找到最优解。具体步骤如下：

1. 状态表示：用二维数组 tmp[i][0] 记录第 i 个舱室已放的标本数，tmp[i][1..2] 记录标本质量。
2. 递归搜索：对每个标本尝试放入所有未满的舱室（最多2个标本），递归处理下一个标本。
3. 回溯优化：递归后撤销当前选择，尝试其他分配方式。
4. 最优解更新：计算每种分配方案的不平衡度，保留最小值及对应的分配方案。

三、代码实现

#include <iostream>
#include <iomanip>
#include <cstring>
#include <cmath>
using namespace std;

double da[100];       // 存储标本质量
int m, n;             // m为舱室数，n为标本数
double am;            // 平均质量
double tmp[20][10];   // 临时存储当前分配方案（tmp[i][0]为舱室i的标本数，tmp[i][1..2]为质量）
double jg[20][10];    // 存储最优分配方案
double mn = -1.0;     // 最小不平衡度，初始化为-1表示未找到

// 深度优先搜索函数，x为当前处理的标本索引
void dfs(int x) {
    if (x >= n) { // 所有标本分配完毕
        double jl = 0.0; // 计算当前方案的不平衡度
        for (int i = 0; i < m; ++i) {
            double sum = 0.0;
            for (int j = 0; j < tmp[i][0]; ++j) {
                sum += tmp[i][j + 1]; // 累加舱室i的质量
            }
            jl += fabs(sum - am); // 计算与平均值的绝对差
        }
        // 更新最优解
        if (mn == -1 || jl < mn) {
            mn = jl;
            memcpy(jg, tmp, sizeof(tmp)); // 复制最优方案
        }
        return;
    }
    // 尝试将第x个标本放入每个舱室
    for (int i = 0; i < m; ++i) {
        if (tmp[i][0] < 2) { // 舱室i未满（最多放2个）
            tmp[i][tmp[i][0] + 1] = da[x]; // 放入标本
            tmp[i][0]++; // 标本数加1
            dfs(x + 1); // 处理下一个标本
            tmp[i][0]--; // 回溯，撤销当前选择
        }
    }
}

int main() {
    int tag = 1; // 测试用例编号
    while (cin >> m >> n) { // 循环读取输入
        am = 0.0;
        for (int i = 0; i < n; ++i) {
            cin >> da[i];
            am += da[i]; // 计算总质量
        }
        am /= m; // 计算平均质量
        memset(tmp, 0, sizeof(tmp)); // 初始化临时方案
        memset(jg, 0, sizeof(jg)); // 初始化最优方案
        mn = -1.0; // 重置最小不平衡度
        dfs(0); // 从第0个标本开始分配
        
        // 输出结果
        cout << "Set #" << tag++ << endl;
        for (int i = 0; i < m; ++i) {
            cout << " " << i << ":"; // 输出舱室编号
            for (int j = 0; j < jg[i][0]; ++j) {
                cout << " " << static_cast<int>(jg[i][j + 1]); // 输出标本质量（转为整数）
            }
            cout << endl;
        }
        cout << fixed << setprecision(5) << "IMBALANCE = " << mn << endl << endl;
    }
    return 0;
}

四、代码解析

1. 输入处理：读取舱室数 m、标本数 n 和标本质量，计算平均质量 am。
2. DFS 递归：
   • 终止条件：所有标本分配完毕，计算当前方案的不平衡度，更新最优解。
   • 递归过程：对每个标本，尝试放入所有未满的舱室，递归处理下一个标本后回溯。
3. 最优解存储：使用 memcpy 复制当前最优方案到 jg 数组，确保记录完整的分配结果。
4. 输出格式：按题目要求输出舱室分配情况和不平衡度，保留5位小数。

五、注意事项

1. 回溯法的正确性：通过撤销当前选择（tmp[i][0]--），确保所有可能的分配方案都被枚举。
2. 数据类型处理：使用 double 存储质量和平均质量，避免整数除法误差。
3. 边界情况：当舱室未放满2个标本时（如只放1个或0个），需正确处理空值。
4. 效率分析：对于 ( C=5 )、( S=10 )，每个标本有 ( 5 \times (2 - \text{已放数}) ) 种选择，总复杂度为 ( O(5^{10}) )，在题目约束下可行。

该方法通过暴力枚举确保找到最优解，适用于小规模数据场景，是解决此类组合优化问题的经典思路。