题意理解

输入分为两部分，第一部分是候选人姓名；第二部分是每张选票对应候选人姓名。如果选票中候选人姓名正确，则对应候选人加一票，否则该票是不合法选票。

方法一

搜索法。 使用name数组存储候选人姓名，vote数组存储对应编号的候选人票数。每输入一张选票，就遍历一遍name数组。如果找到对应候选人，则将其票数加1；如果遍历完了还未找到，则不合法票数加1。

查找过程示意图如下：

具体代码如下：

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int main()
{
    int n,m;
    while(cin>>n)
    {
        int invalid=0;
        vector<string> name;
        string s;
        vector<int> vote(n,0);
        for (int i=0;i<n;i++)
        {
            cin>>s;
            name.push_back(s);
        }
        cin>>m;
        for (int i=0;i<m;i++)
        {
            cin>>s;
            int j;
            for (j=0;j<n;j++)
            {
                //查找对应的候选人
                if (name[j]==s)
                {
                    vote[j]++;
                    break;
                }
            }
            //如果没找到，说明是不合法的票。
            if (j==n) invalid++;
        }
        for (int i=0;i<n;i++) cout<<name[i]<<" : "<<vote[i]<<endl;
        cout<<"Invalid : "<<invalid<<endl;
    }
    return 0;
}

时间复杂度： $O(NMK)O(NMK)$。其中N是候选人人数，M是选票的张数，K是候选人姓名长度。 空间复杂度： $O(N)O(N)$。使用两个长度为N的数组分别记录姓名和对应的选票数。

方法二

哈希表。 使用unordered_map数据结构来保存候选人姓名和对应的选票数，再使用find()函数可以缩短查找的时间。

具体代码如下：

#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>

using namespace std;

int main()
{
    int n,m;
    while(cin>>n)
    {
        int invalid=0;
        vector<string> name;//用来记录候选人输入的顺序
        unordered_map<string, int> select;
        string s;
        for (int i=0;i<n;i++)
        {
            cin>>s;
            name.push_back(s);
            select[s] = 0;
        }
        cin>>m;
        for (int i=0;i<m;i++)
        {
            cin>>s;
            //使用find函数查找选票填写的姓名是否合法
            if (select.find(s)!=select.end())
            {
                select[s]++;
            }
            else invalid++;
        }
        for (int i=0;i<n;i++) cout<<name[i]<<" : "<<select[name[i]]<<endl;
        cout<<"Invalid : "<<invalid<<endl;
    }
    return 0;
}

时间复杂度： $O(N+MK)O(N+MK)$。使用unordered_map查找的时间每次为O(1)。 空间复杂度： $O(N)O(N)$。name数组和select哈希表的长度为候选人人数。