取数游戏 - C++ 代码实现及分析

取数游戏 - 算法分析与 C++ 实现

题目描述

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

算法分析

这道题可以发现，每行只能取一次，所以对于每一行，我们只能取当前剩余的最小值。因此可以考虑按照从小到大的顺序，对每一行记录当前最小值和次小值，然后每一轮取完当前最小值，更新剩余的最小值和次小值。

具体实现可以用堆来维护每一行的最小值和次小值，每轮取完当前最小值之后，将次小值作为新的最小值，然后再从矩阵中取出下一个数，加入堆中，以此类推。

C++ 代码实现cpp#include #include #include using namespace std;

struct Node { int val; int row; int col; bool operator<(const Node& other) const { return val > other.val; // 使用大根堆 }};

int main() { int n; cin >> n; vector<vector> a(n, vector(n)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> a[i][j]; } }

priority_queue<Node> pq;    for (int i = 0; i < n; i++) {        pq.push({a[i][0], i, 0}); // 将每行第一个元素加入堆    }

long long totalScore = 0;    for (int round = 1; round <= n; round++) {        long long sum = 0;        vector<Node> taken; // 记录本轮已取的数字        for (int i = 0; i < n; i++) {            Node top = pq.top();            pq.pop();            sum += top.val;            taken.push_back(top); // 将已取的数字记录下来        }        totalScore += round * sum;

    for (auto& node : taken) { // 将已取的数字的下一位加入堆            if (node.col + 1 < n) {                pq.push({a[node.row][node.col + 1], node.row, node.col + 1});            }        }    }

cout << totalScore << endl;    return 0;}

代码分析

1. 使用 priority_queue 实现大根堆，用于维护每一行的最小值和次小值。2. 初始化时，将每行第一个元素加入堆中。3. 每一轮遍历堆，取出当前最小值，并将该数字所在的行的下一位数字加入堆中，以此类推。4. 最后累加每一轮的得分，得到总得分。

优化

由于每轮都需要取出 n 个最小值，因此可以考虑使用更快的堆实现方式，例如使用二叉堆或 Fibonacci 堆。

总结

这道题考察了贪心算法和堆数据结构的使用，通过合理的分析和算法实现，可以高效地求解出最大总得分