取数游戏：最大得分算法解析及C++代码实现

题目描述

给出一个 n x n 的矩阵，进行取数游戏。取数共 n 轮，第 i 轮需要从每行分别取一个没取过的数字，设取出的数字总和是 s，则第 i 轮的实际得分是 i * s。求 n 轮取数的最大总得分。

输入格式

从标准输入读入数据。第一行输入一个正整数 n（n <= 100）。接下来 n 行，每行输入 n 个正整数 a[i][j]（a[i][j] <= 10^6），构成一个矩阵。

输出格式

输出到标准输出。输出一个整数，表示最大总得分。

样例 #1

样例输入 #1

样例输出 #1

算法解析

要获得最大总得分，我们需要在每轮选择最小的数字来保证总和最小，同时尽量让后面的轮次乘以更大的系数。因此，算法如下：

对每行进行排序，找到每行最小的数字。
对所有最小的数字进行排序，并从最小的开始选择，依次乘以 1, 2, 3...n。

C++ 代码实现

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

int main() {
    int n, a[101][101];
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> a[i][j];
        }
        sort(a[i], a[i] + n); // 对每行排序
    }
    vector<int> min_nums(n); // 存储每行的最小数字
    for (int i = 0; i < n; ++i) {
        min_nums[i] = a[i][0];
    }
    sort(min_nums.begin(), min_nums.end()); // 对最小数字排序
    int s = 0;
    for (int i = 0; i < n; ++i) {
        s += (i + 1) * min_nums[i]; // 计算总得分
    }
    cout << s << endl;
    return 0;
}