C++ 取数游戏算法详解：最大得分策略与代码实现

题目描述

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

输入格式

从标准输入读入数据。第一行输入一个正整数 $n$（$n \le 100$）。接下来 $n$ 行，每行输入 $n$ 个正整数 $a_{ij}$（$a_{ij} \le 10^6$），构成一个矩阵。

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

算法思路

为了获得最大总得分，我们应该在每轮选择当前所有未选数字中最大的数字。可以使用贪心算法来实现。

C++ 代码实现

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

const int N = 110;

struct Num {
    int x, y;
    bool operator<(const Num& t) const {
        return x > t.x;
    }
} num[N * N];

int a[N][N];
bool st[N][N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            num[i * n - n + j] = { a[i][j], j };

    sort(num + 1, num + n * n + 1);

    long long res = 0;
    for (int i = 1; i <= n; i++) {
        int k = (i - 1) * n;
        for (int j = 1; j <= n; j++) {
            int x = num[++k].x, y = num[k].y;
            while (st[y][x]) x = num[++k].x;
            st[y][x] = true;
            res += i * x;
        }
    }

    cout << res << endl;

    return 0;
}

代码解释

结构体 Num：用于存储每个数字的值 x 和它所在的行号 y，重载了 < 运算符，使得排序时按照数字值降序排列。
数组 a：存储输入的矩阵。
数组 st：标记每个数字是否已被选择，初始值为 false。
排序：对 num 数组进行排序，将所有数字按照值从大到小排列。
贪心选择：依次从排序后的 num 数组中选择当前最大的数字，并标记其所在的行和列为已选择。
计算得分：每轮选择数字后，将当前轮数乘以选出的数字之和，并累加到 res 中。

优化说明

使用结构体存储数字和行号，方便排序和选择。
使用 st 数组标记已选数字，避免重复选择。
使用 long long 类型存储得分，防止溢出。

总结

本文介绍了取数游戏的算法思路和 C++ 代码实现，并解释了代码中关键部分的作用。通过贪心策略和结构体排序，我们可以高效地找到取数游戏的最大总得分。希望本文能帮助读者理解算法并灵活运用到实际问题中。