题解

本题的核心是将宝物公平地分配给寻宝者，公平的定义是使每个寻宝者所获宝物的最高感知总价值与最低感知总价值之间的差值最小。可以使用回溯法来生成所有可能的宝物分配方案，然后计算每种方案下的差值，选择差值最小的方案作为最终分配方案。

代码（c++）

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

vector<vector<int> > best_assignment;
int min_diff;

void backtrack(int treasure_idx, int t, int h, 
               vector<vector<int> >& values, 
               vector<vector<int> >& current_assignment) {
    if (treasure_idx == t) {
        // 计算每个猎人的总估值
        vector<int> totals(h, 0);
        for (int i = 0; i < h; ++i) {
            for (size_t j = 0; j < current_assignment[i].size(); ++j) {
                totals[i] += values[i][current_assignment[i][j]];
            }
        }
        
        int curr_max = *max_element(totals.begin(), totals.end());
        int curr_min = *min_element(totals.begin(), totals.end());
        int diff = curr_max - curr_min;
        
        // 更新最优解
        if (diff < min_diff) {
            min_diff = diff;
            best_assignment = current_assignment;
        }
        return;
    }

    // 尝试将当前宝藏分配给每个猎人
    for (int hunter = 0; hunter < h; ++hunter) {
        current_assignment[hunter].push_back(treasure_idx);
        backtrack(treasure_idx + 1, t, h, values, current_assignment);
        current_assignment[hunter].pop_back();
    }
}

int main() {
    string line;
    while (cin >> line, line == "START") {
        int t, h;
        cin >> t >> h;
        
        vector<vector<int> > values(h, vector<int>(t));
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < t; ++j) {
                cin >> values[i][j];
            }
        }
        
        cin >> line; // 读取"END"
        
        // 初始化全局变量
        min_diff = INT_MAX;
        vector<vector<int> > current_assignment(h);
        best_assignment.clear();
        
        // 回溯搜索
        backtrack(0, t, h, values, current_assignment);
        
        // 输出结果
        for (int i = 0; i < h; ++i) {
            sort(best_assignment[i].begin(), best_assignment[i].end());
            for (size_t j = 0; j < best_assignment[i].size(); ++j) {
                cout << best_assignment[i][j] + 1 << " ";
            }
            int total = 0;
            for (size_t j = 0; j < best_assignment[i].size(); ++j) {
                total += values[i][best_assignment[i][j]];
            }
            cout << total << endl;
        }
        cout << endl; // 组间空行
    }
    return 0;
}

代码解释

回溯函数 backtrack：用于生成所有可能的宝物分配方案。对于每个宝物，尝试将其分配给每个寻宝者，然后递归调用自身处理下一个宝物。当所有宝物都分配完毕后，计算当前分配方案下每个寻宝者的总价值，并更新最小差值和最优分配方案。

main 函数：读取输入数据，调用 backtrack 函数生成最优分配方案，最后调用 printResult 函数输出结果。