题解 P6402 【[COCI2014-2015#2] UTRKA】

· · 题解

第 010 篇题解。

Analysis

本题是 map 练习题。

std::map 定义于头文件 <map>，是有序键值对容器，它的元素的键是唯一的。用比较函数 Compare 排序键。搜索、移除和插入操作拥有对数复杂度。 map 通常实现为红黑树。

——摘自「C++ Reference std::map」

可以把 std::map 看作一个映射，即第一个值（关键字，\rm{key}）唯一对应着第二个值（值，\rm{value}）。

std::map 可以存储任意类型的数据，这解决了数组中不能出现「负下标」、「字符串下标」等问题。所以是一个常用的容器。

有关 std::map 的更多信息，可以点开上面的链接看。

对于这个题，用数组存名字和是否完成肯定是不现实的，因为不支持「字符串下标」。所以就要使用 std::map。

map <string, int> participant;

这句话定义了映射，std::string 类型的关键字（名字）对应着 int 类型的值（名字出现的次数）。

接着，对每个选手进行统计。由于 参赛者的名字不一定是唯一的 ，需要递加名字出现的次数。

participant[name[i]]++;

这句话对于输入的名字出现次数作了递加。

然后，输入了完成比赛的选手个数。这时需要把每个完成的选手名字出现的次数递减。

participant[task_completed_name]--;

递减完了，剩下的那个没有归零的就是没完成的。

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <map>

using namespace std;

const int N = 1e5 + 10;
const int M = 30;

map <string, int> participant;
string name[N];
int n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> name[i];
        participant[name[i]]++;
    }
    for (int i = 1; i <= n - 1; i++) {
        string task_completed_name;
        cin >> task_completed_name;
        participant[task_completed_name]--;
    }
    for (int i = 1; i <= n; i++) {
        if (participant[name[i]]) {
            cout << name[i];
            break;
        }
    }
    return 0;
}

The end.