2.6 高效算法设计
本节选解习题来源于《算法竞赛入门经典（第2版）》一书的第8章。
习题8-1 装箱（Bin Packing，SWERC 2005，UVa1149）
给定N（N≤105）个物品的重量Li，背包的容量M，同时要求每个背包最多装两个物品。求至少要多少个背包才能装下所有的物品。
【分析】
先对N个物体按照重量从大到小排序。依次进行决策。在没放好的物体中，考虑最重的i，它应该和谁放一起呢？选择最轻的j，如果i＋j都放不到一个背包里，那i只能单独放，否则就把i和j放在一起。
在考虑i时，如果有多个j都可以和i放在一起，那么选择最轻的j是不是最优策略？对于所有比j重的k来说，在i决策完之后考虑的物体，重量小于i，所以k依然可以和i之后的物体放在一起，不会多占背包。完整程序如下：
习题8-2 聚会游戏（Party Games，Mid-Atlantic 2012，UVa1610）
输入一个n（2≤n≤1000，n是偶数）个字符串的集合D，找一个字符串（不一定在D中出现）S，使得D中恰好一半串≤S，另一半串＞S。如果有多解，输出字典序最小的解。例如，对于｛JOSEPHINE，JERRY｝，输出JF；对于｛FRED，FREDDIE｝，输出FRED。
【分析】
记n＝2k。首先对D进行递增排序，所求的字符串P一定满足Dk≤P＜Dk＋1，则问题就变成寻找符合这个条件的最短并且字典序最小的字符串。记Dk的长度为L，则P的长度一定不大于L。参考暴力搜索的思路，从P的最左边第0位到第L-1位逐步从小到大尝试构造每一位的字符。对于第i位，开始令P［i］＝‘A‘，只要满足P［i］≤‘Z‘且P＜Dk，就一直令P［i］递增。这样构造出来的P［i］如果满足P［i］≤‘Z‘且Dk≤P＜Dk＋1，则说明构造完成，否则继续构造下一位。每一位构造完成之后所得的P就是所求的解。完整程序如下：
习题8-4 奖品的价值（Erasing and Winning，UVa11491）
你是一个电视节目的获奖嘉宾。主持人在黑板上写出一个N位整数（不以0开头），并邀请你恰好删除其中的D个数字。剩下的整数便是你所得到的奖品的价值。自然地，你希望这个奖品价值尽量大。1≤D＜N≤105。
【分析】
令E＝N–D，则本题就是要从输入的整数中选择E个数字，使得组成的整数最大。可以连续选择E次最左边的最大数字，还要给后续的选择留够位数，每次选择的位置为pos，则下次选择的范围就从pos＋1开始。
注意有一个子操作：从一个区间内选择最左边的最大数字。因为N和D的规模都比较大，如果每次线性查找，最坏情况下的时间复杂度会达到O（N2）级别，对于输入的规模是无法接受的(1)。可以做如下的预处理：对于每个位置i以及d∈［0，9］，记录在区间［i…］内第一个d出现的位置NEXT［i］［d］。这个预处理可以在O（10n）的时间内完成，然后上述子操作就可以在O（9）的时间内完成。
完整程序如下：
习题8-5 折纸痕（Paper Folding, UVa177）
你喜欢折纸吗？给你一张很大的纸，对折以后再对折，再对折……每次对折都是从右往左折，因此在折了很多次以后，原先的大纸会变成一个窄窄的纸条。现在把这个纸条沿着折纸的痕迹打开，每次都只打开“一半”，即把每个痕迹做成一个直角，那么从纸的一端沿着和纸面平行的方向看过去，会看到一个美妙的曲线，如图2.43所示。
图2.43
例如，如果你对折了4次，那么打开以后你将看到如图2.43所示的曲线。注意，该曲线是不自交的，虽然有两个转折点重合。给出对折的次数，请编程绘出打开后生成的曲线。
【分析】
看到题目很多读者应该会和笔者一样，首先想到去直接模拟折叠过程。
但经过思考可以发现一个关键点：可以忽略折叠的过程。直接从一条水平的单位长度的线段开始张开，每次张开都是把已有的所有线段首先围绕一个点顺时针旋转90°，然后再和旋转之前的线段一起组合成为新的图形。每次旋转的过程中，需要维护两个点的坐标：起始点s和旋转中心点rot。每次旋转，原先的s不变，s经过旋转之后的那个点成为新的rot，如图2.44所示。
图2.44
旋转的次数就是输入的n。
当把所有最终线段的坐标模拟出来之后，就剩下输出的问题。有一种比较简便的处理方法就是扫描所有的线段，将其x坐标放大一倍，然后垂直类型线段的x坐标再减1。判断平面上每个点是否有垂直或者水平线段，记录对应的字符。最后再扫描平面上的每个点，输出之前记录的字符即可。
完整程序如下：
习题8-6 起重机（Crane，ACM/ICPC CERC 2013，UVa1611）
输入一个1～n（1≤n≤10000）的排列，用不超过96次操作把它变成升序。每次操作都可以选一个长度为偶数的连续区间，交换前一半和后一半。如输入5, 4, 6, 3, 2, 1，可以执行1, 2先变成4, 5, 6, 3, 2, 1，然后执行4, 5变成4, 5, 6, 2, 3, 1，然后执行5, 6变成4, 5, 6, 2, 1, 3，然后执行4, 5变成4, 5, 6, 1, 2, 3，最后执行操作1,6即可。
提示：
2n次操作就足够了。
【分析】
这道题目要求排序，但是基本操作却是“交换一个偶数长度的连续区间的前后两半”，依然可以使用冒泡排序的思路，依次把1到n的每个数归位。
遍历到数字i时，此时1～i-1已经排好序，在未排序的区间（长度是n-i+1）中，记i前面的元素个数为ci，则有以下两种情况。
（1）ci≤(n-i+1)/2，那么可以通过将i前面的未排序区间（记其长度为ci）和从i开始长度为ci的区间进行交换，即可把i交换到第i个位置。
（2）否则，如果n-i+1是偶数，交换前后两半，然后按照情况1处理即可。如果n-i+1是奇数，则忽略第一个元素（肯定不是i），交换剩下长度为偶数的区间的前后两半。
这样在≤2n次操作之内就可以完成。
对于输入数据(5 4 6 3 2 1)，算法的运行过程示意图如下，其中灰色表示未排序区间。
完整程序如下：
习题8-8 猜名次（Guess, ACM/ICPC Beijing 2006, UVa1612）
有n（n≤16384）位选手参加编程比赛。比赛有3道题目，每个选手的每道题目都有一个评测之前的预得分（这个分数和选手提交程序的时间相关：提交得越早，预得分越大）。接下来是系统测试。如果某道题目未通过测试，则该题的实际得分为0分，否则得分等于预得分。得分相同的选手，ID小的排在前面。
给出所有3n个得分以及最后的实际名次，问是否可能。如果可能，输出最后一名的最高可能得分。每个预得分均为小于1000的非负整数，最多保留两位小数。
【分析】
考虑每个选手，每道题目的得分有两种可能（预得分或0），那么总得分就是23=8种可能。输入时，就计算每个选手的这8种得分并且从大到小排序。
第一名的得分选择为8个得分中的最大值，然后按照名次从前到后遍历每个选手，从其8个可能得分中选择满足以下条件的最大得分：
（1）小于上个选手的得分。
（2）或者等于上一个选手的得分且ID小于其ID。
如果选择成功，则这个得分必定是当前选手符合输入名次的最大可能得分。如果失败，说明这个名次无法构造，直接退出。所有选手选择成功后，直接输出最后一个选手选择的得分。
需要注意的是，虽然分数是浮点数，但是题目标明了只有小数点后两位。所以可以直接乘以100转换为整数，最后输出时再除以100。为了避免转换误差，在输入时作为字符串输入，然后再读取为两个int。输出时做类似的处理。完整程序（C++11）如下：
习题8-11 高速公路（Highway, ACM/ICPC SEERC 2005, UVa1615）
给定平面上n（n≤105）个点和一个值D，要求在x轴上选出尽量少的点，使得对于给定的每个点，都有一个选出的点离它的欧几里得距离不超过D。
【分析】
对于每个指定的点P，X轴上符合要求的点刚好组成X轴和圆（P,D）相交的那根弦所对应的区间。那么题目就转换为，在一系列的区间内选择最少的点，使得每个区间内都有点被选中。具体的思路可参考《算法竞赛入门经典（第2版）》中的第8.4.2节。
习题8-14 商队抢劫者（Caravan Robbers, ACM/ICPC NEERC 2012, UVa1616）
输入n条线段，把每条线段变成原线段的一条子线段，使得变之后所有线段等长且不相交（但是端点可以重合）。输出最大长度（用分数表示）。例如，有3条线段[2,6]、[1,4]、[8,12]，则最优方案是分别变成[3.5,6]、[1,3.5]、[8,10.5]，输出5/2。
【分析】
首先把所有线段按照左端点从小到大进行排序，然后使用二分法来计算子线段的最大长度。对于长度L，针对每一个原线段[a,b]，尽量选择靠左的区间作为子线段，如果子线段的左端点max(a,lb)+L > b，那么选择失败，其中lb是上一个选择的子线段的右端点。如果每个线段选择成功，那么L有效。
但是需要注意以下几点：
（1）二分开始要选择尽量窄的一个起始区间，可以选择为[1, 1000000/n]。
（2）二分的迭代次数50次就足够，无须将区间缩小到足够小的范围，否则会超时。
（3）选择输出目标的有理数时，遍历所有可能的分母（就是1～n），然后根据分母以及算出的长度来选择分子。最后选择误差最小的分子分母组合来输出，输出之前都要除去二者的最大公约数。
完整程序如下：
习题8-16 弱键（Weak Key，ACM/ICPC Seoul 2004，UVa1618）
给k（4≤k≤5000）个整数组成的序列Ni，判断是否存在4个整数Np、Nq、Nr和Ns（1≤p＜q＜r＜s≤k），使得Nq＞Ns＞Np＞Nr或者Nq＜Ns＜Np＜Nr。
【分析】
首先对输入序列做预处理，对于每个Ni，记录两个序列Hi和Li。Hi包含所有的j，j＞ i且Nj＞ Ni。Li包含所有j，j满足j＞i且Nj＜Ni。
然后就是遍历所有的p，依次选择可能的q、r、s。
以Nq＜Ns＜Np＜Nr为例：
（1）q肯定在Lp中，在其中进行遍历。
（2）p、q确定之后，r肯定在Hp中并且r＞q，使用upper_bound在Hp中查找所有可能的r。
（3）p、q、r确定之后，s肯定在Hq以及Lp中，并且s＞r，使用upper_bound查找结合binary_search判断。
依次进行查找，如果查找到s说明有解。查找的过程中判断数字是否在某个序列中并且大于一个数，都可以使用二分查找。可以使用STL中的binary_search和upper_bound。完整程序如下：
习题8-17 最短子序列（Smallest Sub-Array，UVa11536）
有n（n≤106）个0～m-1（m≤1000）的整数组成一个序列。输入k（k≤100），你的任务是找一个尽量短的连续子序列（xa，xa＋1，xa＋2，…，xb-1，xb），使得该子序列包含1～k的所有整数。
例如n＝20，m＝12，k＝4，序列为1（2 3 7 1 12 9 11 9 6 3 7 5 4）5 3 1 10 3 3，括号内部分是最优解。如果不存在满足条件的连续子序列，输出“sequence nai”（不含引号）。
【分析】
使用滑动区间的思路，维护一个区间［L，R］，以及一个map，其中包含了［L，R］所有1～k的整数，及其出现的次数。需要注意的是，map中只插入1～k的整数。则当map大小为k时［L，R］就是一个符合要求的区间。
首先L＝0，不断增加R，直到map的大小等于k为止，当map的大小为k时，只要L对应的整数x不在1～k的范围内或者x在map中出现的次数大于1，就可以安全地从区间中删除x，如此反复，当无法继续删除L时，就是一个潜在的最小区间。
当发现一个最小区间之后，就把L加1，让区间向右滑动，然后再寻找小区间。如此在滑动的过程中记录下出现的最短区间。完整程序如下：
习题8-18 感觉不错（Feel Good，ACM/ICPC NEERC 2005，UVa1619）
给一个长度为n（n≤100000）的非负整数序列ai，求出一段连续子序列al，…ar，使得（al＋…＋ar）*min｛al，…，ar｝尽量大。
【分析】
对于一个区间［l，r］来说，我们称所求的值为它的权值。假如ar＋1不是［l，r＋1］区间的唯一最小值，那么［l，r＋1］的权值一定大于［l，r］的。对于每个i，假如能让ai成为最小值的最大区间是［li，ri］，则只需要对所有的［li，ri］求权值比较即可。
首先需要预处理出以下数组：
（1）A的前缀和数组S，其中
。
（2）L和R数组，其中Li表示i左边离i最近且比ai小的元素位置。Ri就是i右边离i最近的比ai小的元素。让ai成为最小值的最大连续区间就是［Li，Ri］。
其中第二个预处理的单调栈算法如下（以Li为例）。
首先，在数组A前后各附加1个0。使用一个栈S，初始为空。从左到右把所有下标i＝1～n入栈，每个下标i入栈之前，首先把所有aj≥ai的下标j出栈，之后，栈顶就是左边最接近并且小于ai的元素下标，也就是Li的值。处理完即可得到L数组。
以A＝｛3，1，6，4，5，2｝为例，演示此算法的运行过程。
初始S＝｛｝，A＝｛0，3，1，6，4，5，2，0｝
i=1:A［1］=3, L［1］=0, S=｛1｝
i=2:A［2］=1, L［2］=0, S=｛2｝
i=3:A［3］=6, L［3］=2, S=｛2,3｝
i=4:A［4］=4, L［4］=2, S=｛2,4｝
i=5:A［5］=5, L［5］=4, S=｛2,4,5｝
i=6:A［6］=2, L［6］=2, S=｛2,6｝
再用类似的逻辑从右到左处理一次即可得到R数组。预处理完成后，计算所有ai*（SLi＋1-SRi）的最大值即可。需要注意的是，可能会有一种特殊情况就是全部元素为0，则所求结果就是0，所在区间为［1，1］，需要进行特殊处理。完整程序（C＋＋11）如下：
习题8-19 球场（Cricket Field，ACM/ICPC NEERC 2002，UVa1312）
一个W*H（1≤W，H≤10000）网格里有n（0≤n≤100）棵树，要求找一个最大空正方形，如图2.45所示。
【分析】
注意网格的长宽都很大，直接枚举正方形的边界（时间复杂度为100003）会超时。但是树只有最多100棵，且正方形内部肯定不能包含树。另外，最大正方形一定是有至少两条边都经过一棵树（包括网格边界），如图2.46所示，否则很容易构造出更大的正方形。
图2.45
图2.46
遍历正方形的边界。首先对所有树的Y坐标排序去重（使用set即可），得到一个正方形可能的上下边的Y坐标集合，再对所有树的坐标按照X进行排序。
枚举正方形的上下边的Y坐标。对于每一对Y坐标（minY，maxY），初始的正方形左边界为left＝0（操场左边）。对于所有的树坐标P，如果P．y恰好正在枚举的上下边界之间，那么就发现一个新的正方形位于（left，P．x）以及（minY，maxY）相交形成的区域内，更新答案。同时更新P．x为下一个正方形的左边界。时间复杂度是O（n3）。注意整个网格的边界也可以理解为树，不要忘记处理。完整程序如下：
习题8-24 龙头滴水（Faucet Flow，UVa10366）
x＝0的正上方有一个水龙头，以每秒1单位体积的速度往下滴水。x＝-1，-3，…，leftx和x＝1，3，5，…，rightx处各有一个挡板，高度已知。求经过多长时间以后水会流出最左边的挡板或者最右边的挡板。如图2.47所示，leftx＝-3，rightx＝3，4个挡板高度分别为4、3、2、1，则6秒钟之后水会从最右边的挡板溢出。
图2.47
输入第一行为两个奇数leftx和rightx（leftx≤-1，rightx≥1），接下来的各个正整数表示从左到右各个挡板的高度。挡板个数不超过1000。
【分析】
首先引入一个关键的结论：
如果有两个挡板X和Y（如图2.48所示），X不高于Y，那么从X左边的水如果要流到Y，在接触到Y之前，会形成一个阶梯形状。也就是说，从X流到Y所需要的时间就是阶梯下方的面积。
回到题目本身，考虑X＝0的左右两边最高的挡板高度LH、RH，以及其位置LHi、RHi（如果有多个，就取离X＝0最近的那个）。
如果LH＝RH，那么说明水流会在两边都溢出来。那么就计算水从LHi流到最左边挡板所需要的时间Lt，以及从RHi流到最右边挡板所需要的时间Rt。因为两边同时在流，所求的结果就是水把LHi-RHi这个区间的矩形装满所需要的时间再加上min（Lt＋Rt）*2。
如果LH＜RH，假设Ti是X＝0右边第一个高度≥LH的，如图2.49所示。
图2.48
图2.49
那么水一定是首先接触到左边缘。而且水流分两部分，一部分从Ti流到Ti右边第一个高度大于LH的挡板的位置这里，另一部分从LHi向左溢出流到左边缘。假设前者所需水量为rt，后者所需为lt。
（1）如果lt＞rt，那么所求结果就是：LHi和Ti之间高度为LH的矩形对应的水量也就是（LHi＋Ti）*LH＋lt＋rt。
（2）如果lt≤rt，rt对应的部分只能灌满lt的水，左边就已经溢出了，所求结果就是：（LHi＋Ti）*LH＋2*lt。
LH＞ RH时的讨论可以类比以上情况。
为了简化处理，可以先假设两个挡板之间距离为1，最后求出结果之后再乘以2输出即可。完整程序如下：
习题8-25 有向图D和E（From D to E and back，UVa11175）
对一个有n个结点的有向图D，可以构造这样一个图E，即D的每条边对应E的一个结点（例如，若D有一条边uv，则E有个结点的名字叫uv），对于D的两条边uv和vw，E中的两个结点uv和vw之间连一条有向边。E中不包含其他边。
输入一个m个结点k条边的图E（0≤m≤300），判断是否存在对应的图D。E中各个结点编号为0～m-1。
提示：
虽然题目中m≤300，实际上可以解决规模远超过这个限制的问题。
【分析】
在E图中，如果存在i和j结点到x都有边，而i和j中只有一个结点到y有边，则这个图E不可能转化来，因为在D中一条边不可能指向两个点（读者可以参考图2.50来思考）。因此暴力枚举i、j和x判断是否可行即可。
图2.50
注意：
笔者无法构造上述做法的严格性证明，但是也无法找到反例(2)。
完整程序（C＋＋11）如下：
习题8-26 找黑圆（Finding ［B］lack Circles，Rujia Liu's Present 6，UVa12559）
输入一个h*w的黑白图像（30≤w，h≤100），你的任务是找出图像中的圆。每个像素都是1*1的正方形，左上角像素的中心坐标为（0，0），右下角像素的中心坐标为（w-1，h-1）。对于一个圆，它的圆周穿过（只是接触到像素边界不算）的像素都会被涂黑（用1表示）。没有被任何圆穿过的像素仍然是白色（用0表示）。圆心保证在整点处，半径保证是1～5的整数。最多有2%的黑点会变成白点。
提示：
方法有多种，尽情发挥创造力吧。
【分析】
因为数据量不是特别大，所有可能的圆的个数上限是50*30*100，可以考虑进行暴力搜索每一种可能的半径以及坐标（r，x，y）。
对于（r，x，y）来说，要循环判断圆上的每个点，因为边上的点最多也就是100个。可以遍历100个圆心角角度对应的点来判断，为了提高速度，可以采用如下技巧：
（1）随机取100个角度，看看这个角度对应的边上的点是不是存在。
（2）如果已经判断超过10个且有一半不符合，说明一定不存在对应的圆，直接返回即可。
完整程序如下：
