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

题目描述

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

代码实现

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

const int N = 110;

int n;
int a[N][N];

struct node {
    int v, id;
    bool operator< (const node& t) const {
        return v > t.v;
    }
} b[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            b[j] = {a[i][j], j};
        }
        sort(b + 1, b + n + 1);
        ans += b[1].v * i;
    }
    cout << ans << endl;
    return 0;
}

代码解析

1. 结构体定义: 定义了一个 node 结构体，用于存储每个数字的值 v 和其在矩阵中的位置 id。
2. 排序: 对于每一行，将数字按照值从大到小排序，并使用结构体 node 存储排序后的值和位置信息。
3. 计算得分: 每次迭代选择当前行中最大值（即 b[1].v），并将该值乘以当前轮数 i，累加到总得分 ans 中。

总结

该代码使用结构体和排序算法实现了取数游戏最大得分计算，代码简洁高效。

相关内容

• 贪心算法
• 排序算法
• C++ 结构体