题意
已知 \(n\) 场比赛前 \(m\) 名的名字,每场比赛前 \(10\) 名各有不同的分数,求以下两种排名方法排名第一的人的名字。
- 按照分数排序,若分数相同,第 \(1\) 次数多的优先,若第 \(1\) 次数相同,第 \(2\) 次数多的优先,直至比出为止。
- 先按排在第 \(1\) 的次数多的优先,次数相同则按照分数排序,分数相同的按照第 \(2\) 的次数排序,直至比出为止。
解题方法
数据范围很小,我们模拟即可。
首先,存储的问题我们用结构体解决。
struct node
{
string name; //名字
int score, rk[51]; //得分以及各个排名的次数
} a[1005];
第一种比较函数(按照分数排序,若分数相同,第 \(1\) 次数多的优先,若第 \(1\) 次数相同,第 \(2\) 次数多的优先,直至比出为止)。
bool cmp(node a, node b)
{
if (a.score != b.score) return a.score > b.score; //按分数排序
for (int j = 1; j <= 50; j ++) if (a.rk[j] != b.rk[j]) return a.rk[j] > b.rk[j]; //从大到小按照排名次数排序
}
第二种比较函数(先按排在第 \(1\) 的次数排序,次数相同则按照分数排序,分数相同的按照第 \(2\)的次数排序,还相同的按排在第 \(3\) 的次数排序,直至比出为止)。
bool csp(node a, node b)
{
if (a.rk[1] != b.rk[1]) return a.rk[1] > b.rk[1]; //按第1的次数排序
if (a.score != b.score) return a.score > b.score; //按分数排序
for (int j = 2; j <= 50; j ++) if (a.rk[j] != b.rk[j]) return a.rk[j] > b.rk[j]; //从大到小按照排名次数排序
}
至于楼上楼下的几位大佬,为什么要用两次快排呢?这不是平白无故的给时间复杂的加上一个 \(log\) 吗?两次循环直接取最优的那个不香吗?
#include <bits/stdc++.h>
using namespace std;
struct node
{
string name; //名字
int score, rk[51]; //得分以及各个排名的次数
} a[1005];
int n, cnt, f[51] = {0, 25, 18, 15, 12, 10, 8, 6, 4, 2, 1}, i;
bool find(string s)
{
for (int j = 1; j <= cnt; j ++)
if (a[j].name == s)
{
a[j].score += f[i];
a[j].rk[i] ++;
return true;
}
return false;
}
bool cmp(node a, node b)
{
if (a.score != b.score) return a.score > b.score; //按分数排序
for (int j = 1; j <= 50; j ++) if (a.rk[j] != b.rk[j]) return a.rk[j] > b.rk[j]; //从大到小按照排名次数排序
}
bool csp(node a, node b)
{
if (a.rk[1] != b.rk[1]) return a.rk[1] > b.rk[1]; //按第1的次数排序
if (a.score != b.score) return a.score > b.score; //按分数排序
for (int j = 2; j <= 50; j ++) if (a.rk[j] != b.rk[j]) return a.rk[j] > b.rk[j]; //从大到小按照排名次数排序
}
int main()
{
scanf("%d", &n);
while (n --)
{
int m;
scanf("%d", &m);
for (i = 1; i <= m; i ++)
{
string s;
cin >> s;
if (!find(s))
{
a[++ cnt].name = s;
a[cnt].score = f[i];
a[cnt].rk[i] = 1;
}
}
}
node ans = a[1];
for (int j = 2; j <= cnt; j ++) if (cmp(a[j], ans)) ans = a[j]; //第一种方法比较
cout << ans.name << endl;
ans = a[1];
for (int j = 2; j <= cnt; j ++) if (csp(a[j], ans)) ans = a[j]; //第二种方法比较
cout << ans.name;
}
本小学蒟蒻的第一篇蓝题题解,请大家多多关照。
管理员同志过年审题解辛苦了!