取数游戏 - C++ 代码实现

取数游戏 - 算法解析与 C++ 代码**题目描述:**给出一个 n*n 的矩阵，进行取数游戏。取数共 n 轮，第 i 轮需要从每行分别取一个没取过的数字，设取出的数字总和是 s，则第 i 轮的实际得分是 i/*s。求 n 轮取数的最大总得分。**输入格式:**从标准输入读入数据。第一行输入一个正整数 n（n<=100）。接下来 n 行，每行输入 n 个正整数 a_{ij}（a_{ij}<=10^6），构成一个矩阵。**输出格式:**输出到标准输出。输出一个整数，表示最大总得分。**样例 #1:****样例输入 #1:31 3 24 2 41 3 1样例输出 #1:48算法思路:**这道题可以使用贪心算法来解决。我们可以通过每一轮选择当前行中最大的数字来获得最大的得分。**C++ 代码实现:**cpp#include #include using namespace std;const int N = 110;int n;int w[N][N];int col[N];int main(){ cin >> n; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) cin >> w[i][j]; int res = 0; for (int i = 1; i <= n; i ++ ) { int k = 0; for (int j = 1; j <= n; j ++ ) if (!col[j] && (!k || w[i][j] > w[i][k])) k = j; col[k] = true; res += w[i][k] * i; } cout << res << endl; return 0;}**代码解析:**1. 使用 col 数组记录每一列是否已经被选中。2. 每一轮遍历当前行，找到最大且未被选中的数字。3. 将该数字所在列标记为已选中，并计算当前轮的得分。4. 最后累加所有轮的得分，得到最大总得分。**优化后的代码:**为了简化代码，我们可以直接在原矩阵中标记已选数字，避免使用额外的 col 数组。cpp#include #include using namespace std;const int N = 110;int n;int w[N][N];int main(){ cin >> n; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) cin >> w[i][j]; int res = 0; for (int i = 1; i <= n; i ++ ) { int k = 0; for (int j = 1; j <= n; j ++ ) if (w[i][j] != -1 && (!k || w[i][j] > w[i][k])) k = j; w[i][k] = -1; // 标记为已选中 res += w[i][k] * i; } cout << res << endl; return 0;}**总结:**这道题的贪心算法思路简单易懂，代码实现也比较容易。通过优化代码，我们可以进一步提高代码的简洁性和效率