题目描述
石头剪子布,是一种猜拳游戏。起源于中国,然后传到日本、朝鲜等地,随着亚欧贸易的不断发展它传到了欧洲,到了近现代逐渐风靡世界。简单明了的规则,使得石头剪子布没有任何规则漏洞可钻,单次玩法比拼运气,多回合玩法比拼心理博弈,使得石头剪子布这个古老的游戏同时用于“意外”与“技术”两种特性,深受世界人民喜爱。
游戏规则:石头打剪刀(用 G 表示石头),布包石头(用 C 表示布),剪刀剪布(用 P 表示剪刀)。
现在有 $2n$ 名选手进行两两猜拳,一共进行 $m$ 轮,选手编号为$1∼2n$,初始时,所有选手的排名按照编号从小到大排列。小猴有预知未来的能力,知道第 $j$ 轮中编号为 $i$ 的选手出结果为$g_{i,j}$ 其中$g_{i,j}$ 为 $G$、$C$、$P$ 三者之一。
每轮比赛中共会进行 $n$ 场比赛,都是让最新的排名(按照分数从高到低排序,如果有分数相同的情况,则按编号从小到大排序)中的第 $1$ 名与第 $2$ 名比赛(第一场比赛)、第 $3$ 名与第 $4$ 名比赛(第二场比赛)、
…、第 $2k−1$ 名与第 $2k$ 名比赛(第 $k$ 场比赛,其中 $1≤k≤n$)。
每场比赛中的结果均为:
- 一名选手获胜,另一名选手输,获胜方选手得 $1$ 分,输得一方选手不得分;
- 双方平局,双方选手均不得分。
小猴因为使用超能力预知每名选手出的结果,现在需要休息,所以请你计算并输出第 $m$ 轮结束时所有人的排名,即按照分数从高到低输出每名选手的编号,如果有分数相同的情况,则优先输出编号更小的选手。
【输入格式】
第一行,包含两个整数 $n,m$。
接下来 $2n$ 行,每行包含 $m$ 个字符组成的字符串,其中第 $i$ 行第 $j$ 列的字符表示第 $j$ 轮中第 $i$ 名选手出的结果。
【输出格式】
共 $2n$ 行,每行一个整数,其中第 $i$ 行表示排名为 $i$ 的选手的编号。
【输入输出样例#1】
输入#1
2 3
GCP
PPG
PCC
GPC
输出#1
1
4
2
3
【输入输出样例#2】
输入#2
2 2
PG
PP
CG
GC
输出#2
2
3
1
4
解题思路
- 定义一个结构体,里面有$2$个值,$r$ 和 $score$ 代表编号和分数,初始化结构体
- 根据排名判断对战,再根据输赢记录分数
- 根据分数从大到小排序,如果分数相同,则按编号从小到大排序
C++代码
#include <iostream>
#include <algorithm>
using namespace std;
char g[1005][1005];
struct Per {
int r, score;
}per[1005];
bool judge(char x, char y) { // 判断输赢函数
if (x == 'C' && y == 'G') return 1;
if (x == 'P' && y == 'C') return 1;
if (x == 'G' && y == 'P') return 1;
return 0;
}
bool cmp(Per x, Per y) { // 排序规则
if (x.score != y.score) return x.score > y.score;
return x.r < y.r;
}
int main() {
int n, m, cur = 0;
cin >> n >> m;
n *= 2;
for (int i = 1; i <= n; i++) { // 输入
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
}
}
for (int i = 1; i <= n; i++) { // 初始化结构体
per[i].r = i;
per[i].score = 0;
}
for (int j = 1; j <= m; j++) {
for (int i = 1; i <= n; i += 2) {
// 判断输赢,记录分数
int x = per[i].r;
int y = per[i + 1].r;
per[i].score += judge(g[x][j], g[y][j]);
per[i + 1].score += judge(g[y][j], g[x][j]);
}
// 根据排序规则排序
sort(per + 1, per + n + 1, cmp);
}
for (int i = 1; i <= n; i++) { // 输出
cout << per[i].r << endl;
}
return 0;
}