取数游戏：贪心算法解题 - C++ 代码实现

取数游戏：贪心算法解题 - C++ 代码实现

题目描述

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

输入格式

从标准输入读入数据。 第一行输入一个正整数 'n' ('n' ≤ 100)。 接下来 'n' 行，每行输入 'n' 个正整数 'a_ij' ('a_ij' ≤ 10⁶)，构成一个矩阵。

输出格式

输出到标准输出。 输出一个整数，表示最大总得分。

样例 #1

样例输入 #1

3
1 3 2
4 2 4
1 3 1

样例输出 #1

48

算法

算法2: 贪心算法

(贪心) O(n²)

将每行最大的数找到，并将这些最大值从大到小排个序，然后第 'i' 轮取第 'i' 大的数即可。

时间复杂度

O(n²)

C++ 代码

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

const int MAXN = 100;
int n, a[MAXN][MAXN], max_val[MAXN];

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