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

取数游戏：贪心算法求解最大得分题目描述给出一个 $n/times n$ 的矩阵，进行取数游戏。/取数共 $n$ 轮，第 $i$ 轮需要从每行分别取一个没取过的数字，设取出的数字总和是 $s$，则第 $i$ 轮的实际得分是 $i/times s$。/求 $n$ 轮取数的最大总得分。输入格式从标准输入读入数据。/第一行输入一个正整数 $n$（$n/le100$）。/接下来 $n$ 行，每行输入 $n$ 个正整数 $a_{ij}$（$a_{ij}/le10^6$），构成一个矩阵。输出格式输出到标准输出。/输出一个整数，表示最大总得分。样例 #1****样例输入 #131 3 24 2 41 3 1样例输出 #148解题思路本题可以使用贪心算法来解决，每次取每一行中剩余未取过的最大数字即可。具体来说，可以维护一个 $n$ 个元素的数组 $used$，表示第 $i$ 行是否已经取过数字，初始时所有元素均为 $0$。然后进行 $n$ 轮取数，每轮取数时，遍历所有行，找到未被取过的最大数字，记录下其所在行和列，同时将 $used$ 数组中对应的元素置为 $1$，表示该行已经取过数字。遍历完所有行后，将该轮得分加入总得分中即可。C++ 代码c++#include #include using namespace std;const int MAXN = 100;int n;int a[MAXN][MAXN];bool used[MAXN];int main() { cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> a[i][j]; } } int ans = 0; for (int i = 1; i <= n; i++) { int max_val = 0, max_row = -1, max_col = -1; for (int j = 0; j < n; j++) { if (!used[j] && a[j][max_col] < a[j][i - 1]) { max_val = a[j][i - 1]; max_row = j; max_col = i - 1; } } used[max_row] = true; ans += i * max_val; } cout << ans << endl; return 0;}代码分析1. 首先，定义一个二维数组 $a$ 来存储输入的矩阵，以及一个布尔型数组 $used$ 来记录每一行是否被取过。2. 然后，进行 $n$ 轮取数，每轮取数时，用两个变量 $max/_val$ 和 $max/_row$ 分别记录当前轮最大值和最大值所在的行。3. 在每轮取数的循环中，遍历所有行，找到未被取过的最大数字，更新 $max/_val$ 和 $max/_row$。4. 找到最大值后，将对应的行标记为已取过，并将最大值乘以当前轮数加到总得分中。5. 最后，输出总得分。时间复杂度该算法的时间复杂度为 $O(n^2)$，因为需要遍历整个矩阵 $n$ 次