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

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

题目描述

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

输入格式

从标准输入读入数据。第一行输入一个正整数 $n$（$n \le 100$）。接下来 $n$ 行，每行输入 $n$ 个正整数 $a_{ij}$（$a_{ij} \le 10^6$），构成一个矩阵。

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

思路

对于每一行，找到最小值和次小值，然后比较两个数的大小，将较小的数加到得分中并将它的下标记录下来。这样第一轮得分就可以确定下来。

接下来，我们需要找到下一轮的数字，此时我们只需要在上一轮中未被选中的数字中，找到最小值和次小值，就可以将下一轮的数字确定下来。

根据得分的计算方式，我们可以发现，如果一个数在前几轮中被选了，那么这个数的分值就会越来越大，越来越有优势，因此我们需要保证每一轮中所取的数都是当前可选数字中的最小值或次小值。

因此，我们可以将当前最小值和次小值所在的列删除，这样，下一轮如果要选取当前最小值或次小值所在的行的数字时，就只能选取列中剩下的数字，从而保证了所选的数字是当前可选数字中的最小值或次小值。

时间复杂度：$O(n^3)$

C++ 代码

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

int main() {
    int n;
    cin >> n;
    int a[101][101];
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> a[i][j];
        }
    }
    int score = 0;
    int chosen[101][101] = {0}; // 记录每个数字是否被选中
    for (int i = 1; i <= n; ++i) {
        int min1 = 1000001, min2 = 1000001;
        int min1_idx = 0, min2_idx = 0;
        for (int j = 1; j <= n; ++j) {
            if (!chosen[i][j] && a[i][j] < min1) {
                min2 = min1;
                min2_idx = min1_idx;
                min1 = a[i][j];
                min1_idx = j;
            } else if (!chosen[i][j] && a[i][j] < min2) {
                min2 = a[i][j];
                min2_idx = j;
            }
        }
        if (min1 < min2) {
            score += i * min1;
            chosen[i][min1_idx] = 1;
        } else {
            score += i * min2;
            chosen[i][min2_idx] = 1;
        }
        // 删除最小值和次小值所在的列
        for (int k = 1; k <= n; ++k) {
            chosen[k][min1_idx] = 1;
            chosen[k][min2_idx] = 1;
        }
    }
    cout << score << endl;
    return 0;
}