取数游戏：贪心算法求解最大总得分

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

代码实现 (C++)

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

const int MAXN = 100;

int n;
long long a[MAXN][MAXN], b[MAXN]; // 使用long long类型保证数据范围

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    long long ans = 0;
    for (int i = 0; i < n; i++) { // 每一轮
        for (int j = 0; j < n; j++) { // 从每行选择最大值
            b[j] = a[j][i];
        }
        sort(b, b + n); // 将每行选出的最大值排序
        for (int j = n - 1; j >= 0; j--) { // 从大到小取数
            ans += (i + 1) * b[j];
            break; // 每一轮只取一个数
        }
    }
    cout << ans << endl;
    return 0;
}

解释

思路：贪心+排序

每一轮都要从每行取一个数，我们可以从每行中选出一个最大的数，然后将这些数从大到小排序，第 'i' 轮就从排序后的数中取第 'i' 大的数。

因为每行只能取一个数，所以我们可以通过排序，每次取每行中最大的数，这样就可以保证每轮都能取到最优解。
代码实现
- 使用 long long 类型来存储数据，以避免数据溢出问题。
- 使用循环遍历每一行，找出每行的最大值并存储到 b 数组中。
- 使用 sort 函数对 b 数组进行排序。
- 从排序后的 b 数组中从大到小取数，并将取出的数乘以当前轮数得到当前轮的得分，累加到 ans 中。
时间复杂度：O(n^2logn)
- 遍历矩阵需要 O(n^2) 时间复杂度。
- 排序需要 O(nlogn) 时间复杂度。
- 总时间复杂度为 O(n^2logn)。

总结

本题使用贪心算法和排序，通过每次选择每行最大值并排序，保证了每轮都取得最优解，最终得到了 'n' 轮取数的最大总得分。代码清晰易懂，并使用 long long 类型避免了数据溢出问题。