题意分析

本题描述的是加拿大某个特定选区的选票统计问题。已知该选区有若干候选人，每个候选人要么隶属于某个政党，要么是独立候选人。题目会给出候选人的名字以及他们所属的政党信息，接着会给出若干张选票，每张选票上记录了所选候选人的名字。需要根据这些选票统计每个候选人的得票数，从而确定获胜候选人所属的政党。若不存在获胜者（即没有候选人获得的选票数比其他所有候选人都多），则输出 “tie”。

解题思路

1. 数据存储：使用两个 $map$ 分别存储候选人名字与所属政党的映射关系，以及候选人名字与得票数的映射关系。
2. 输入处理：
   • 首先读取候选人的数量 $n$，然后循环 $n$ 次，每次读取候选人名字和所属政党名字，并将其存储到 $map1$ 中。
   • 接着读取选票的数量 $m$，再循环 $m$ 次，每次读取一张选票上所选候选人的名字，若该候选人在候选人名单中，则将其得票数加 1。
3. 统计获胜者：在统计选票的过程中，记录当前得票数最多的候选人信息，包括其名字和得票数。同时，使用一个标志 $flag$ 来判断是否存在唯一的获胜者。若当前候选人的得票数超过之前记录的最大得票数，则更新最大得票数和获胜候选人名字，并将 $flag$ 置为 $true$；若当前候选人的得票数等于最大得票数，则将 $flag$ 置为 $false$，表示可能存在平局。
4. 输出结果：根据 $flag$ 的值输出结果。若 $flag$ 为 $true$，表示存在唯一的获胜者，输出该获胜者所属的政党名字；若 $flag$ 为 $false$，表示存在平局，输出 “tie”。

代码解释

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>
#include <map>
#define eps 1e-8
#define op operator
#define MOD  10009
#define MAXN  100100

#define FOR(i,a,b)  for(int i=a;i<=b;i++)
#define FOV(i,a,b)  for(int i=a;i>=b;i--)
#define REP(i,a,b)  for(int i=a;i<b;i++)
#define REV(i,a,b)  for(int i=a-1;i>=b;i--)
#define MEM(a,x)    memset(a,x,sizeof a)
#define ll __int64

using namespace std;

map <string,string> map1;//存储人名和党派
map <string,int> map2;//存储人名和票数

int main()
{
    //freopen("ceshi.txt","r",stdin);
    int n;
    scanf("%d",&n);
    getchar(); // 消耗掉 scanf 后的换行符
    string s1,s2;
    for(int i=0;i<n;i++)
    {
        getline(cin,s1); // 读取候选人名字
        getline(cin,s2); // 读取候选人所属政党名字
        map1[s1]=s2; // 将候选人名字和所属政党名字存入 map1
    }
    int m;
    scanf("%d",&m);
    getchar(); // 消耗掉 scanf 后的换行符
    int mx=0; // 记录最大得票数
    int tmp;
    bool flag=0; // 标志是否存在唯一的获胜者
    while(m--)
    {
        getline(cin,s1); // 读取一张选票上所选候选人的名字
        map2[s1]++; // 该候选人得票数加 1
        tmp=map2[s1]; // 获取该候选人当前得票数
        if(mx<tmp)
        {
            mx=tmp;  flag=1;   s2=s1; // 更新最大得票数、标志和获胜候选人名字
        }
        else  if(tmp==mx)  flag=0; // 若当前得票数等于最大得票数，标志置为 false
    }
    if(flag)  cout<<map1[s2]<<endl; // 若存在唯一的获胜者，输出其所属政党名字
    else  printf("tie\n"); // 若存在平局，输出 "tie"
    return 0;
}

复杂度分析

• 时间复杂度：$O(n + m)$，其中 $n$ 是候选人的数量，$m$ 是选票的数量。主要时间开销在于读取输入数据和统计选票。
• 空间复杂度：$O(n)$，主要用于存储候选人名字与所属政党的映射关系以及候选人名字与得票数的映射关系。

注意事项

1. 输入处理：由于使用 $scanf$ 读取整数后会留下换行符，需要使用 $getchar()$ 消耗掉该换行符，否则后续的 $getline$ 会读取到换行符而导致输入错误。
2. 边界条件：要确保输入的候选人名字和政党名字不重复，且所有行都没有前导或尾随空格。
3. 平局判断：在统计选票时，要正确处理平局的情况，通过 $flag$ 标志来判断是否存在唯一的获胜者。