上海计算机学会2024年7月月赛C++乙组T2选举快报
发布时间
阅读量：
阅读量
选举快报
内存限制: 256 Mb时间限制: 1000 ms
题目描述
在一场选举过程中，n 张选票依次打开，给定每张选票提名的候选者姓名，请统计在每打开一张选票后，谁是当下得票最高的候选者。
若两名候选者得票数量一样多，输出字典序排名靠前的候选者名字。
输入格式
- 第一行：单个整数：表示 n
- 第二行到第 n+1 行：第 i+1 行有一个字符串 sisi 表示第 ii 张选票提名的候选人，保证 si 只含英文字母。
输出格式
共 n 行：在第 i 行，输出第 i 张选票打开后，最领先的候选人姓名。
数据范围
- 30% 的数据，1≤n≤100
- 60% 的数据，1≤n≤50,000
- 100% 的数据，1≤n≤300,000
样例数据
输入:
4
Tom
Jerry
Tom
Jerry
输出:
Tom
Jerry
Tom
Jerry
解析：暴力法，时间复杂度O(m^2)，m为被选举人人数：
详见代码：
#include <bits/stdc++.h>
using namespace std;
struct node {
string name;
int num;
};
node a[300005];
int n;
int cnt = 0;//获得选票的候选人人数
int mx = 0;//最多获得票数
string name;//获得最多票数的候选人名字
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
string s;
cin >> s;
bool flag = 0;//假设是第一次获得选票
for(int j = 1; j <= cnt; j++) {//枚举已经得票的被选举人
if (a[j].name == s) {//找到
a[j].num++;//票数加一
flag = 1;//非第一次获得选票
}
//求最大值
if (a[j].num > mx || a[j].num == mx && a[j].name < name) {
mx = a[j].num;
name = a[j].name;
}
}
if (flag == 0) {//如果是第一次获得选票
cnt++;
a[cnt].name = s;
a[cnt].num = 1;
}
//取最大值
if (a[cnt].num > mx || a[cnt].num == mx && a[cnt].name < name) {
mx = a[cnt].num;
name = a[cnt].name;
}
cout << name << "\n";
}
return 0;
}
使用map保存候选人，则可以将时间复杂度提升到O(MlogM)，M为候选人人数，
详见代码：
#include <bits/stdc++.h>
using namespace std;
map <string, int> mp;
int n;
int mx = 0;//最多获得票数
string name;//获得最多票数的候选人名字
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
string s;
cin >> s;
mp[s]++;
if (mp[s] > mx || mp[s] == mx && s < name) {
mx = mp[s];
name = s;
}
cout << name << "\n";
}
return 0;
}
全部评论 (0)
还没有任何评论哟~