2.3　C++与STL入门

本节选解习题来源于《算法竞赛入门经典（第2版）》一书的第5章。

本章的习题主要是为了练习C++语言以及STL，程序本身并不一定很复杂。建议读者至少完成8道习题。如果想达到更好的效果，建议完成12题或以上。

习题5-1　代码对齐（Alignment of Code, ACM/ICPC NEERC 2010, UVa1593）

输入若干行代码，要求各列单词的左边界对齐且尽量靠左。单词之间至少要空一格。每个单词不超过80个字符，每行不超过180个字符，一共最多1000行，如图2.17所示。

【分析】

可以将所有的单词看作一个表格，则每一行被空格串切分成多个列。每一列的宽度就是表格中当前列的最长单词的宽度。输出时，列与列之间用一个空格分开。

建议使用STL的I/O流，读一行使用getline(cin,line)，其中line是string。对line的切分，可以使用stringstream。切分过程中，更新每一列单词的最大长度。输出时可用setw来设置一个输出对象的宽度。具体可以查询STL使用手册。完整程序如下：

习题5-2　Ducci序列（Ducci Sequence, ACM/ICPC Seoul 2009, UVa1594）

对于一个n元组(a₁,a₂,…,a_n)，可以对每个数求出它和下一个数的差的绝对值，得到一个新的n元组(|a₁-a₂|,|a₂-a₃|,…,|a_n-a₁|)。重复这个过程，得到的序列称为Ducci序列，例如：

(8, 11, 2, 7) → (3, 9, 5, 1) → (6, 4, 4, 2) → (2, 0, 2, 4) → (2, 2, 2, 2) → (0, 0, 0, 0)

也有的Ducci序列会一直循环。输入n元组（3≤n≤15），你的任务是判断它最终会变成0还是会一直循环。输入保证最多1000步就会变成0或者循环。

【分析】

序列可以直接使用vector<int>模拟，vector本身已经重载了等号运算符对两个容器的内容进行比较。所以判重和判是否全0直接用“==”操作符即可，判重可以使用set < vector<int> >。完整程序如下：

习题5-3　卡片游戏（Throwing cards away I, UVa10935）

桌上有n（n≤50）张牌，从第一张牌（即位于顶面的牌）开始从上往下依次编号为1～n。当至少还剩两张牌时进行以下操作：把第一张牌扔掉，然后把新的第一张放到整叠牌的最后。输入每行包含一个n，输出每次扔掉的牌，以及最后剩下的牌。

【分析】

因为对牌堆的操作就是出队和入队，直接使用STL里面的queue来模拟牌堆即可。需要注意的特殊情况是，当n=1时，直接输出“Discarded cards:”，行尾是不包含空格的。完整程序如下：

习题5-4　交换学生（Foreign Exchange, UVa10763）

有n（1≤n≤500000）个学生想交换到其他学校学习。为了简单起见，规定每个想从A学校换到B学校的学生必须找一个想从B换到A的“搭档”。如果每个人都能找到自己的搭档（一个人不能当多个人的搭档），学校就会同意他们交换。每个学生用两个整数A、B表示，你的任务是判断交换是否可以进行。

【分析】

对于每所学校，如果要交换成功，必须要出去和要进来的人数完全相等。可以在输入的同时记每一个A和B组成的整数对，以及对应的A→B的交换学生个数。

输入完成后，遍历所有的（A,B），看看对应的学生个数是否和（B,A）的相同，若有不同，则交换不能进行。完整程序（C++11）如下：

习题5-5　复合词（Compound Words，UVa 10391）

给一个词典，找出所有的复合词，即恰好有两个单词连接而成的单词。输入每行都是一个由小写字母组成的单词。输入已按照字典序从小到大排序，且不超过120 000个单词。输出所有复合词，按照字典序从小到大排列。

【分析】

使用set＜string＞来存储所有单词，然后对每个单词的所有左右切分方案进行遍历，判断切分出来的两个子字符串两边是否同时存在于set中，符合条件的直接输出即可。这里set中的字符串已经按照默认字典序排序。完整程序如下：

习题5-6　对称轴（Symmetry，ACM/ICPC Seoul 2004，UVa1595）

给出平面上N（N≤1000）个点，问是否可以找到一条竖线使得所有点左右对称。如图2.18所示，左边的图形有对称轴，右边没有。

【分析】

如果存在对称轴x＝m，那么m一定是所有点x坐标的平均值。首先在输入每个点坐标的同时就求出m。然后遍历每一个点p，要么p.x＝m就是说p关于x＝m的对称点就是自身，或者p关于x＝m的对称点也在输入的点中，否则说明对称轴不存在。

在输入时就需要对所有的点建立索引，可以使用Point类，同时使用set＜Point＞来存储所有的点，为此Point类需要重载“＜”比较运算符。

习题5-7　打印队列（Printer Queue，ACM/ICPCNWERC 2006，UVa12100）

学生会里只有一台打印机，但是有很多东西需要打印，因此打印任务不可避免的需要等待。有些打印任务比较急，有些不那么急，所以每个任务都有一个1～9的优先级，越大表示任务越急。

打印机的运作方式如下：首先从打印队列里取出一个任务J，如果队列里有比J更急的任务，则直接把J放到打印队列尾部，否则打印任务J（此时不会把它放回打印队列）。

输入打印队列中各个任务的优先级以及你所关注的任务在队列中的位置（队首位置为0），输出该任务完成的时刻。所有任务都需要1分钟打印。例如，打印队列为｛1，1，9，1，1，1｝，目前处于队首的任务最终完成时刻为5。

【分析】

使用STL中的queue来模拟打印队列，同时因为需要判断是否有更急的任务，那么就需要使用一个pCnt数组来维护每个优先级p在当前队列中对应的任务的数量，需要在队列变化时更新这个pCnt数组。完整程序如下：

习题5-8　图书管理系统（Borrowers，ACM/ICPC World Finals 1994，UVa230）

你的任务是模拟一个图书管理系统。首先输入若干图书的标题和作者（标题各不相同，以END结束），然后是若干指令：BORROW指令借书，RETURN指令还书。对于SHELVE指令，把所有已归还但还未上架的图书排序后依次插入到架子上并输出图书标题和插入位置（可能是第一本书或者某本书的后面）。

图书排序的方法是先按作者从小到大排，再按标题从小到大排。在处理第一条指令之前，你应当先将所有图书按照这种方式排序。

【分析】

首先建立一个Book类，使用一个vector＜Book＞来保存所有的图书。同时使用map＜string，int＞建立一个标题到图书编号（其在vector中的位置）的映射，方便根据标题来查找图书。

使用两个set＜int＞来分别保存已归还但是还未上架的书籍shelf，以及还在书架上的书籍lib。set的第二个泛型参数（用于指定set内部对于Book类的排序规则）要使用一个函数对象（functor）来对其中的书籍位置按照题目要求的规则进行排序。

这样借书还书时直接对shelf和lib进行操作即可。上架时，每次在lib中插入一个元素之后，可以取到这个元素在set中的位置iterator，然后对这个iterator进行自减操作即可拿到插入的书籍所在位置前面的一本书。完整代码如下：

习题5-9　找bug（Bug Hunt，ACM/ICPC Tokyo 2007，UVa1596）

输入并模拟执行一段程序，输出第一个bug所在行。每行程序有两种可能。

• □　数组定义：格式为arr［size］。如a［10］或者b［5］，可用下标分别是0～9和0～4。定义之后所有元素均为未初始化状态。
• □　赋值语句：格式为arr［index］＝value。如a［0］＝3或者a［a［0］］＝a［1］。

赋值语句可能会出现两种bug：下标index越界；使用未初始化的变量（index和value都可能出现这种情况）。

程序不超过1000行，每行不超过80个字符且所有常数均为小于2³¹的非负整数。

【分析】

建立一个Array类，里面包含数组的大小，并且用一个map＜int，int＞来表示初始化过的数组下标和对应的值。用size＝-1表示数组不存在，并且初始map是空的，表示每个位置上的元素均未初始化。之后在对每个语句求值时，递归求出每个表达式的值，然后再进行相应的赋值或者取值。另外，需要特别注意array的size＝0也是合法的。

习题5-10　在Web中搜索（Searching the Web，ACM/ICPC Beijing 2004，UVa1597）

输入n篇文章和m个请求（n＜100，m≤50000），每个请求都是4种格式之一。

• □　A：找包含关键字A的文章。
• □　A AND B：找同时包含关键字A和B的文章。
• □　A OR B：找包含关键字A或B的文章。
• □　NOT A：找不包含关键字A的文章。

处理询问时需要对每篇文章输出证据。前3种询问输出所有至少包含一个关键字的行，第4种询问输出不包含A的整篇文章。关键字只由小写字母组成，查找时忽略大小写。每行不超过80字符，一共不超过1500行。

【分析】

首先在输入时需要对所有的行进行记录，把所有的行字符串放到一个vector＜string＞中，后续对行的处理都通过一个整数索引来进行。

经过仔细观察可以发现，对于一个文章来说，所有的查询都可以归结为如下的操作：对于一个单词w，查询所有包含w的行的序号。由此可以对每一篇文章建立一个结构Doc，里面包含文章中所有的行的序号vector＜int＞ lines，以及一个map＜string，set＜int＞＞ words保存每个单词的所在行号集合。这样在每次插入行时就可以维护words以备后续查询。

这个结构建立起来之后，对于AND和OR查询，就是对查询两个单词输出的两个set＜int＞进行set_union即可。对于NOT查询，符合条件的文章就是查询出来的结果为空的那些。对于每个单词查询，符合条件的文章就是查询出集合不为空的那些。

另外一个技巧就是，针对set＜int＞提供一个operator＜＜的运算符重载，方便对查询出来的行进行输出。具体请参照以下代码：

习题5-11　更新字典（Updating a Dictionary，UVa12504）

在本题中，字典是若干键值对，其中键为小写字母组成的字符串，值为没有前导零或正号的非负整数（因此－4、03和＋77都是非法的。注意该整数可以很大）。输入一个旧字典和一个新字典，计算二者的变化。输入的两个字典中键都是唯一的，但是排列顺序任意。具体格式如下（注意字典格式中不含任何空白字符）：

输入包含两行，各包含不超过100个字符，即旧字典和新字典。输出格式如下。

• □　如果至少有一个新增键，打印一个“＋”号，然后是所有新增键，按字典序从小到大排列。
• □　如果至少有一个删除键，打印一个“-”号，然后是所有删除键，按字典序从小到大排列。
• □　如果至少有一个修改键，打印一个“*”号，然后是所有修改键，按字典序从小到大排列。
• □　如果没有任何修改，输出No changes。

例如，若输入两行分别为｛a：3，b：4，c：10，f：6｝和｛a：3，c：5，d：10，ee：4｝，输出为以下3行：＋d，ee；-b，f；*c。

【分析】

对于每一行，使用一个线性遍历把数据解析成map＜string，string＞，然后对两个map进行对比，就可以判断出所求的3种键。还建议对vector＜string＞重载operator＜＜操作符，方便对比较的结果进行输出：

输出结果的代码就是这样的：

习题5-12　地图查询（Do You Know The Way to San Jose？，ACM/ICPC World Finals 1997，UVa511）

有n张地图（已知名称和某两个对角线端点的坐标）和m个地名（已知名称和坐标），还有q个查询。每张地图都是边平行于坐标轴的矩形，比例定义为高度除以宽度的值。每个查询包含一个地名和详细等级i。假定包含此地名的地图中一共有k种不同的面积，则合法的详细等级为1～k（其中1最不详细，k最详细，面积越小越详细）。如果详细等级i的地图不止一张，则输出地图中心和查询地名最接近的一张；如果还有并列的，地图长宽比应尽量接近0.75（这是Web浏览器的比例）；如果还有并列，查询地名和地图右下角坐标应最远（对应最少的滚动条移动）；如果还有并列，则输出x坐标最小的一个。如果查询的地名不存在或者没有地图包含它，或者包含它的地图总数超过i，应报告查询非法（并且输出包含它的最详细地图名称，如果有的话）。

【分析】

因为牵涉比较多的二维几何计算，可以使用Point类来简化相关代码。首先是定义Map类，包含所有的相关信息（ratio, width, height, area, minx最小x坐标）等，并且需要对所有的地名的坐标建立索引，使用map<string, Point>。

对于每个具体的查询，首先是根据坐标查出包含这个坐标的所有map以及相应的level值，之后需要对这些map进行排序，排序规则如题意所示。首先按照level（也就是面积从小到大）进行排序，level相同按照其他规则进行排序。排序规则可以封装到一个STL的functor对象中去。完整程序如下：

习题5-13　客户中心模拟（Queue and A，ACM/ICPC World Finals 2000，UVa822）

你的任务是模拟一个客户中心运作情况。客服请求一共有n（1≤n≤20）种主题，每种主题用5个整数描述：tid、num、t0、t和dt，其中tid为主题的唯一标识符，num为该主题的请求个数，t0为第一个请求的时刻，t为处理一个请求的时间，dt为相邻两个请求之间的间隔（为了简单情况，假定同一个主题的请求按照相同的间隔到达）。

客户中心有m（1≤m≤5）个客服，每个客服用至少3个整数描述：tid，k，tid₁，tid₂，…，tid_k，表示一个标识符为pid的人可以处理k种主题的请求，按照优先级从大到小依次为tid₁，tid₂，…，tid_k。当一个人有空时，他会按照优先级顺序找到第一个可以处理的请求。如果有多个人同时选中了某个请求，上次开始处理请求的时间早的人优先；如果有并列，id小的优先。输出最后一个请求处理完毕的时刻。

【分析】

核心部分的逻辑是将所有要发生的事情用事件来表示，用优先级队列来维护所有的事件，循环着每次从中取出最早的一个事件，然后按照事件类型进行分类处理：

输入时，每种请求就实现生成num个事件放到事件队列中。模拟的循环中，每个时间点，用multiset＜int＞作为要服务的请求队列，使用multiset是因为队列中可能有相同主题的请求。同时用一个set维护空闲的客服编号。

首先取出所有时间相同的队首事件，挨个进行处理。

（1）如果是请求事件，就放到请求队列。

（2）如果是客服事件，就将客服加到空闲客服集合中。

然后就是针对当前空闲客服以及请求队列中的请求进行匹配处理。

while(请求队列非空& &空闲客服集合非空) {

（1）针对每个请求建立一个集合set<int>，放置所有可以服务此请求的客服编号，编号排序规则参考题目的表述。

（2）先将每个客服按照优先级分配到其能处理的每个任务的集合中。

（3）如果没有进行分配，直接退出while循环。

（4）按照之前分配好的任务集合给客服分配任务，对于每个分配好的客服，要构造一个其变为空闲的事件，放入事件队列。

}

完整程序如下：

此类离散事件模拟类的题目最关键是要掌握事件概念的抽象方法以及优先级队列的使用。习题5-16也可以作为很好的练习题目。

习题5-14　交易所（Exchange, ACM/ICPC NEERC 2006, UVa1598）

你的任务是为交易所设计一个订单处理系统。要求支持如下3种指令。

• □　BUY p q：有人想买，数量为p，价格为q。
• □　SELL p q：有人想卖，数量为p，价格为q。
• □　CANCEL i：取消第i条指令对应的订单（输入保证该指令是BUY或者SELL）。

交易规则如下：对于当前买订单，若当前最低卖价（ask price）低于当前出价，则发生交易；对于当前卖订单，若当前最高买价（bid price）高于当前价格，则发生交易。发生交易时，按供需物品个数的最小值交易。交易后，需修改订单的供需物品个数。当出价或价格相同时，按订单产生的先后顺序发生交易。输入输出细节请参考原题。

【分析】

表面上来看，买卖都是一个优先级队列，但是这里有一个需求就是需要随时从队列中删除一个元素，如果用heap实现（STL中的priority_queue就是基于heap实现），删除的时间会比较长：需要从vector中删除然后重新构造heap。

所以可使用set<int>来实现队列，队列中保存的是Order的编号，先按照价格排序，再按照订单的先后顺序也就是编号的大小排序。因为两个队列的排序规则不同，将两个规则分别封装成为两个functor对象，然后将其作为泛型参数来声明两个不同的set即可。完整程序如下：

习题5-15　Fibonacci的复仇（Revenge of Fibonacci, ACM/ICPC Shanghai 2011, UVa12333）

Fibonacci数的定义为F(0)=F(1)=1，然后从F(2)开始，F(i)=F(i-1)+F(i-2)。例如前10项Fibonacci数分别为1, 1, 2, 3, 5, 8, 13, 21, 34, 55…

有一天晚上，你梦到了Fibonacci，它告诉你一个有趣的Fibonacci数。醒来以后，你只记得它的开头几个数字。你的任务是找出以它开头的最小Fibonacci数的序号。例如以12开头的最小Fibonacci数是F(25)。输入不超过40个数字，输出满足条件的序号。

如果序号为0～100000（不包含100000）的Fibonacci数均不满足条件，输出-1。

【分析】

如果直接用十进制大整数类，计算就会超时。可以使用一万进制的大整数类。依次求出前99999个F数，但是不需要每次保存F数本身，只是把其前40位作为字符串保留下来，存储到一个Trie中去。后续查找就在这个Trie中查找。

关于Trie的介绍请参考《算法竞赛入门经典—训练指南》中的3.3.1节。完整程序如下：

习题5-16　医院设备利用（Use of Hospital Facilities, ACM/ICPC World Finals 1991, UVa212）

医院里有n（n≤10）个手术室和m（m≤30）个恢复室。每个病人首先会被分配到一个手术室，手术后会被分配到一个恢复室。从任意手术室到任意恢复室的时间均为t₁，准备一个手术室和恢复室的时间分别为t₂和t₃（一开始所有手术室和恢复室均准备好，只有接待完一个病人之后才需要为下一个病人准备）。

k名（k≤100）病人按照花名册顺序排队，T点钟准时开放手术室。每当有准备好的手术室时，队首病人进入其中编号最小的手术室。手术结束后，病人应立刻进入编号最小的恢复室。如果有多个病人同时结束手术，编号较小的病人优先进入编号较小的恢复室。输入保证病人无须排队等待恢复室。

输入n、m、T、t₁、t₂、t₃、k和k名病人的名字、手术时间和恢复时间，模拟这个过程。输入输出细节请参考原题。

【分析】

首先是定义事件结构：

类似于习题5-13，可以定义以下几个事件类型：

（1）手术室开始进入空闲状态opFree。

（2）手术室开始进入准备状态opPre。

（3）恢复室开始进入空闲状态reFree。

（4）恢复室开始进入准备状态rePre。

建立几个全局状态：

（1）等待做手术的病人队列opQueue。

（2）等待进恢复室的病人队列reQueue。

（3）空闲手术室队列freeOpRooms。

（4）空闲恢复室队列freeReRooms。

（5）事件队列(使用priority_queue)。

以上1～4全局状态均使用set，因为需要针对编号进行排序，需要注意的是reQueue的排序规则，是按照病人之前做手术时所在的手术室编号进行排序。

整个模拟的过程就是循环地进行事件的处理。

1．处理当前时间的事件

（1）对于opFree，就是将手术室插入freeOpRooms。

（2）对于opPre，说明手术室开始准备，病人做完手术了，需要把这个病人插入reQueue，并且往事件队列中插入一个手术室准备完毕也就是一个opFree的事件。

（3）对于reFree，就是将恢复室插入freeReRooms。

（4）对于rePre，说明病人做完恢复了。往事件队列中插入一个恢复室准备完毕的事件。

2．分别处理opQueue和reQueue

（1）对于opQueue和freeOpRooms，按照题目规则把病人安排到对应的手术室，并且按照病人的手术时间插入opPre事件。同时增加病人以及手术室的对应时间信息。

（2）对于reQueue和freeReRooms，按照题目规则把病人安排到对应的恢复室，并且按照病人的恢复时间插入rePre事件。同时增加病人以及恢复室的对应时间信息。

完整程序如下：