题意

n个人参与被投票，统计每人被投次数，与无效票数量

限制：参与人不大于100，投票总数不大于100

方法

基于STL实现

把题目要求文字内容直接翻译成代码

1. 为了保持输出顺序，所以使用vector来记录输入顺序
2. 为了判断是否出现过，使用set来记录参与人
3. 为了统计每人被投次数，使用map来记录人到被投票的数量关系

因为我们不需要按名字排序，所以上述set和map可以换为hash版本的

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(~scanf("%d",&n)){
        vector<string> sarr; // 参与人 顺序保持 string arr
        unordered_set<string> ss; // 字符串出现统计 string set
        for(int i = 0;i<n;i++){
            string s;
            cin>>s;
            sarr.push_back(s);
            ss.insert(s);
        }
        scanf("%d",&n);
        unordered_map<string,int> s2cnt; // 字符串次数统计 string to count
        int invalid = 0; // 无效票统计
        for(int i = 0;i<n;i++){
            string s;
            cin >> s;
            if(!ss.count(s)){ // 无效票
                invalid++;
            }else{
                s2cnt[s] ++;
            }
        }
        for(auto s:sarr){ // 按初始顺序输出
            printf("%s : %d\n",s.c_str(),s2cnt[s]);
        }
        printf("Invalid : %d\n",invalid);
    }
    return 0;
}

复杂度分析

时间复杂度: 对于每个名字，主要是读入和hash放入map/set 所以时间复杂度为$O(n)O(n)$

空间复杂度: 各个存储空间与读入数据都保持常数倍，所以时间复杂度为$O(n)O(n)$

for套for

我们先记录所有候选人

然后每次收到一张票时，在候选人中查找，找到则计数+1

以题目中的样例数据A B C D为候选人，A D E CF A GG A B为票为例

最后直接输出所有统计即可

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(~scanf("%d",&n)){
        vector<string> sarr; // 参与人 顺序保持
        vector<int>cnt(n,0) ; // 票数统计
        for(int i = 0;i<n;i++){
            string s;
            cin>>s;
            sarr.push_back(s);
        }
        int m;
        scanf("%d",&m);
        int invalid = 0; // 无效票统计
        for(int i = 0;i < m;i++){
            string s;
            cin >> s;
            bool found = false; // 是否找到相等字符串
            for(int j = 0; j < n;j++){
                if(sarr[j] == s){ // 找到候选人
                    cnt[j]++; // 票数+1
                    found = true;
                }
            }
            invalid += !found;
        }
        for(int i = 0 ; i< n;i++){
            printf("%s : %d\n",sarr[i].c_str(),cnt[i]);
        }
        printf("Invalid : %d\n",invalid);
    }
    return 0;
}

复杂度分析

时间复杂度: 对每张票，最坏情况需要遍历所有候选人，所以时间复杂度为$O(n^2)O(n^2)$

空间复杂度: 各个存储空间与读入数据都保持常数倍，所以时间复杂度为$O(n)O(n)$