取数游戏 - 算法题解与 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

解题思路

本题可以使用贪心算法来解决。由于每一轮需要从每行取一个数字，为了使得分最大，我们应该尽可能选择当前轮最大的数字。

因此，我们可以将矩阵中的所有数字按照从大到小排序，然后依次取出最大的数字。为了防止重复取同一行中的数字，我们使用一个二维数组 vis[i][j] 来标记第 $i$ 行第 $j$ 个数字是否已经被取过。

代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=105;
int n,tot,ans;//tot存储已经取过的数的个数，ans存储最大总得分
boool vis[N][N];//vis[i][j]=1表示i这一行j这个数已经取过
struct node{
    int val,pos;//pos存储这个数在第几行
}a[N*N];
boool cmp(node x,node y){
    return x.val>y.val;//按照从大到小排序
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            scanf("%d",&a[tot+1].val);
            a[tot+1].pos=i;
            tot++;
        }
    sort(a+1,a+1+tot,cmp);
    for(int i=1;i<=tot;i++){
        if(!vis[a[i].pos][a[i].val]){
            vis[a[i].pos][a[i].val]=1;
            ans+=a[i].val*i;
        }
    }
    printf("%d\n",ans);
    return 0;
}

代码解释

使用 struct node 结构体存储每个数字的值和所在的行号，方便排序和判断是否重复取数。
使用 sort 函数按照从大到小对 a 数组进行排序。
遍历排序后的数组，如果当前数字所在行还没有被取过，就将该数字标记为已取过，并计算得分。

优化

可以使用优先队列来优化排序的过程，将排序的时间复杂度从 $O(n^2 \log n^2)$ 降到 $O(n^2 \log n)$。
可以使用并查集来优化判断是否重复取数的过程，将判断的时间复杂度从 $O(n^2)$ 降到 $O(n \log n)$。

总结

本题是一道经典的贪心算法问题，通过使用排序和标记的方法可以有效地解决问题。同时，代码中也使用了 struct 结构体和 sort 函数，使代码更加简洁易懂。

希望本题解能够帮助你更好地理解这道题目的解题思路和代码实现。

取数游戏 - 算法题解与C++代码