前言

标准模板库，简称STL，包含有大量的模板类和模板函数，是C升级到C++的++里面包括的部分，非常方便实用，是竞赛中的必备技能之一，当然STL和C++语法一样，想介绍详细，也会变成厚厚的一本书(《 STL源码剖析 》)，所以这和语法的学习方法是一样的，不断学习需要用到的即可，从doc中学习最标准的书写方式，从别人的代码中学习一些奇技淫巧高效的使用方法

C++ Reference

题意

[Greedy Gift Givers]

给定互送礼物的列表，确定每个人收到的礼物价值比送出的多多少

每个人都准备了一些钱来送礼物，而这些钱将会被平均分给那些将收到他的礼物的人

INPUT
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
5
dave
laura
owen
vick
amr
dave
200 3
laura
owen
vick
owen
500 1
dave
amr
150 2
vick
owen
laura
0 2
amr
vick
vick
0 0
OUTPUT
1
2
3
4
5
dave 302
laura 66
owen -359
vick 141
amr -150

题目分析

当你第一次拿到这种题的时候，可能会觉得人名的处理非常的棘手

那么我们先来做一个题目简化，将这些人名全部替换成数字，那么这个问题就变成一个较为简单的模拟题了：读入每个代表人的数字(1到n)，然后读入他准备用于买礼物的钱，准备送的朋友，计算每个朋友收到的礼物价值和这个人的花费，将花费计算并保存在每个人对应的值上(可以用一个数组来存储)，送出去的钱(朋友收到的总和)计负，收到的钱计正相加处理，实现起来应该并不困难

现在每个人的标识从数字变为了字符串，我们需要额外处理的问题是，如何去定位这个人，原来的数字可以作为数组的下标，但是现在字符串不可以，这就是最大的问题，一个朴素的处理方式是，我们先用一个字符串数组保存下人名，即name[0]到name[n-1]保存了所有人的名字，然后用一个money数组来保存值的计算过程，每次处理到人名，我们就在name这个表中去查找，找到之后将其在name中的下标id作为人的标识符，将对应的值计算记录在money[id]上

在name表中查找的过程可以直接用for循环去找，这么处理的时间复杂度是$O(n^2)$的 (时间复杂度是什么，如何计算时间复杂度：搜索相关知识或阅读《算法导论》相关章节)，用哈希表来处理这个过程则可以对复杂度进一步优化时间度到$O(n)$ (学有余力的同学可以自行学习哈希表如何处理此类问题)

接下来我将介绍如何使用STL中的模板函数来解决这个问题

知识点

输入输出流

首先，出于后续处理的考虑，字符串用string类来读入，而不是之前学到过的char数组，string是无法采用c式读入的，所以我们要用cin来处理读入

这里需要说明一下C++输入输出流在竞赛中通常是如何处理的，在C++中，cin和cout默认和stdio同步，即可以和C式读入混用而不会导致指针混乱，但是同步是有代价的，函数需要用到各自的缓冲区，所以速度就会变慢，那么如果想要cin的速度和scanf一样快，则需要取消缓冲区同步，可以简单地通过一行代码做到

1
ios::sync_with_stdio(false);

此外在默认情况下，cin会绑定cout，用于保证输入缓冲区在调用输入之前被刷新，为了进一步加速，我们可以将两者的绑定也取消

1
cin.tie(NULL); // cout.tie(NULL);

STL-vector

向量vector是STL中的一种容器，可以实现动态增长，也就是说，你在定义的时候不需要限定长度，当你往里放入元素的时候容量会自动变大

举个例子，我们定义一个int类型的向量，我们不需要定义其大小，直接里放入元素即可，已经被元素占据的位置可以直接通过下标访问

1
2
3
vector<int> a;
a.push_back(3);
cout << a[0] << "\n";

那么如果我希望直接在下标为5的位置直接放入这个3呢，那不是需要先往里塞入5个0才可以么？这种情况，我们就可以定义一下vector的长度，然后就可以当做数组一样用了

1
2
vector<int> a(10);
a[5] = 3;

STL-map

映射map是STL中的一种容器，底层实现是红黑树，我们在之前分析题目的时候提到，这个题如果把名字从字符串改成编号，我们就可以用数组来存储信息以简单地解决这个问题，那么map在这个题中可以做的事情概括成一句话就是，让字符串可以作为下标

map可以做的事情就是将一种数据类型映射到另一种数据类型，我们知道，对于X集合到Y集合的单射f，有f(x)=y，其中x和y是两个集合中对应的元素。map呢，就是实现了这样一个f，你令f(x)=y，那么x为下标的f值就被指向y，且你可以随时更新f(x)的值，听起来是不是，其实f就像是一个数组

举个例子，将string映射到int

1
2
3
map<string, int> mp;
cin >> name >> money;
mp[name] = money;

代码中name是字符串，而money是数字，也就是说，我们可以将字符串作为下标来建立一个类似数组的东西来处理值了，map的单次查找插入时间为$O(log(n))$，而另有一种STL：unordered_map，底层实现是哈希桶，处理方式和map类似，但是两者在不同的问题规模下各有优劣，同学们可以自行查阅资料学习

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
int main() {
    int np, ng, money;
    
    // 消除缓冲区以及解绑
    ios::sync_with_stdio(false);
    cout.tie(NULL);

    cin >> np;

    // 将string映射到int
    unordered_map<string, int> mp;
    vector<string> name(np);

    // 读入name列表并初始化对应的mp值
    for (int i = 0; i < np; i++) {
        cin >> name[i];
        // mp可以看做是一个字符串为下标的数组
        mp[name[i]] = 0;
    }

    // 按照题目模拟送礼过程
    string giver, receiver;
    for (int i = 0; i < np; i++) {
        cin >> giver >> money >> ng;
        mp[giver] -= money;
        // 特殊判断，防止被零除
        if (ng == 0) continue;
        // 计算每个人分到的钱
        int tmp = money / ng;
        for (int j = 0; j < ng; j++) {
            cin >> receiver;
            mp[receiver] += tmp;
            money -= tmp;
        }
        // 如果钱并不能平均分，则余数没有花出去
        mp[giver] += money;
    }

    // 按照输入顺序输出每个名字和对应的值
    for (int i = 0; i < np; i++) {
        cout << name[i] << " " << mp[name[i]] << endl;
    }
    return 0;
}

Accept

任务清单

  • 用最朴素的方式实现这道题(用数组存储名字，根据字符串查找)
  • 学习并使用map(unordered_map)来完成这道题，了解map的更多用法
  • 学习哈希表(开址法，拉链法(ASL更低))，用自己写的哈希表完成这道题
  • 学习set(multiset)，了解和map用法的区别，各自的优劣