G3016 [GESP202503 三级] 词频统计 题解

知识点：字符串、词频统计、字典序。

解题思路

先将所有单词转为小写，用有序映射累计词频。按字典序遍历，只在频率严格更高时更新答案。

为什么正确

同一词的大小写变体归入同一键；有序遍历中保留最早出现的最高频词就实现字典序最小的平局规则。

易错点

平局时不能用>=更新，否则会选中字典序较大的词。

复杂度

时间O(L+n log n)，空间O(L)，L为总字符数。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    map<string,int>cnt;
    while(n--) {
        string s;
        cin>>s;
        for(char &c:s)c=tolower(c);
        cnt[s]++;
    }
    string ans;
    int best=0;
    for(auto [s,c]:cnt)if(c>best) {
        best=c;
        ans=s;
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。