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

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

C++ 代码实现

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

const int N = 110;

struct node {
    int val, id;
} a[N][N];

bool cmp(node x, node y) {
    return x.val > y.val;
}

int n, ans;
bool st[N];

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

    for (int i = 1; i <= n; i++) {
        sort(a[i] + 1, a[i] + n + 1, cmp);
        for (int j = 1; j <= n; j++) {
            int id = a[i][j].id;
            if (!st[id]) {
                st[id] = true;
                ans += i * a[i][j].val;
                break;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

代码解析

结构体定义: 使用 struct node 来存储每个数字的值 val 和其所在列的索引 id。
排序: 每行使用 sort 函数按 val 值降序排列，以便在每行中选择最大的数字。
标记: 使用 st 数组标记已经选过的列，避免重复选择。
计算得分: 在每轮中，从当前行中选择最大的且未被选过的数字，并将其加入到总得分中。

总结

本代码通过排序和标记实现了一个高效的取数游戏最大得分算法，并使用 struct 提高代码可读性和组织性。