取数游戏 - C++ 高效解法

取数游戏 C++ 高效解法

题目描述

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

C++ 代码cpp#include #include #include

using namespace std;

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

vector rowSums(n); for (int i = 0; i < n; ++i) { rowSums[i] = accumulate(matrix[i].begin(), matrix[i].end(), 0); } sort(rowSums.begin(), rowSums.end(), greater());

int totalScore = 0; for (int i = 0; i < n; ++i) { totalScore += (i + 1) * rowSums[i]; }

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

算法解释

1. 使用 vector 存储矩阵，方便使用迭代器进行操作。2. 使用 accumulate 函数计算每行的和，并存储在 rowSums 向量中。3. 使用 sort 函数对 rowSums 向量进行降序排序，保证每次选择最大的行和。4. 使用 accumulate 函数计算总得分。

代码分析

• 使用 vector 和迭代器方便地操作矩阵数据。* accumulate 函数提供高效的求和操作。* sort 函数对行和进行排序，保证选择最大的数字。

总结

使用 STL 库中的高级函数，可以简化代码，并提高代码效率。在本例中，我们使用了 vector、accumulate 和 sort 函数，使得代码更加简洁易懂