程序员进阶之算法练习（二十五）

前言

算法题是锻炼思维的好工具，在解决问题的层面考察思考能力。

正文

1. Compote

题目链接 题目大意： 给出a、b、c三种材料，可以1:2:4组成d，不能拆分成0.5，问最多有多少材料参与制作。 1个a 2个b 4个c 组成一个d，参与的材料有1+2+4=7。 a,b,c (1 ≤ a,b,c ≤ 1000)

Examples input 2 5 7 output 7 input 4 7 13 output 21 input 2 3 2 output 0

题目解析： 题意非常清晰，暴力的做法是枚举，每次给a/b/c分别减去1/2/4，直到其中一种材料不足。 更快的做法是ans = min(a * 7, min(b / 2 * 7, c / 4 * 7));

2. Decoding

题目链接 题目大意： 定义一个“median letter”的概念： 1、如果字符串长度为奇数，那么为中间的字符； 2、如果字符串长度为偶数，那么为中间偏左的字符；

现在对一个字符串，选择median letter，并且将这个字符拿出来，重复这个操作； 每次取出来的字符串依次排好，得到一个新字符串。 例如：volga 分别取出来的字符是l,o,g,v,a，组成一个新的字符串 logva 。

现在给出字符串的长度n，还有一个字符串str； 求一个字符串strNew，要求strNew按照上面的规则，组成是新字符串是str。

Examples input 5 logva output volga input 2 no output no input 4 abba output baba

题目解析： 先来看这个提取的过程：每次都是选出中间的字符。 那么在恢复原来字符串的时候，只要按照原来的顺序，假设有n个字符串。 那么第一个字符串是n/2, 然后再假设一个left 和 right 指针，然后轮流往两边延伸即可。

核心点：strNew和str相同长度

3.Tram

题目链接 题目大意： 在一条直线上，有一辆公共汽车从点0到点s，不断往返，速度为t1秒每米； 有一个人，要从点x1到点x2，速度为t2秒每米； 当人和车子的位置重叠时，人可以上车，之后可以随时下车；（上下车时间忽略） 现在求人到达目的地的最短时间是多少？

输入数据有三行，分别是： s, x1 and x2 (2 ≤ s ≤ 1000, 0 ≤ x1, x2 ≤ s, x1 ≠ x2) t1 and t2 (1 ≤ t1, t2 ≤ 1000) p and d (1 ≤ p ≤ s - 1, d is either 1 or -1) p表示当前车子所在的位置，d表示方向 只能为1或者-1

Examples input 4 2 4 3 4 1 1 output 8 input 5 4 0 1 2 3 1 output 7

题目解析： 题目有一个很重要的限制 0 ≤ x1, x2 ≤ s， 表示车子的行程最终是会覆盖到x1和x2。 那么，就不会出现人上车后下车再走的情况。 用贪心的策略可以知道，要么一直走到终点站（我们假设时间为time1）； 要么走一段距离，然后上车，直到终点（我们假设时间为time2）。

人直接走到终点的时间为 time1 = t2 * |x2 - x1|; 为了简化计算，第二种情况采用这样的计算方式： 假设人站在x1不动，等着车子来接。 计算车子第一次经过终点的时间，同时考虑这个路程有没有经过点x1； 如果没有再计算车子第二次经过终点的时间，直到有经过点x1，得到时间time2;

ans = min(time1, time2);

巧妙的一个题目，非常喜欢。

4. Green and Black Tea

题目链接 题目大意： 小明喜欢喝茶，每天都要用一个茶包，每个茶包只能用一次； 他有a个绿茶包，b个黑茶包； 小明不喜欢连续喝同一种茶超过k天。 问是否存在适合的茶包分配方案，使得小明能喝到n天。（a+b=n） 如果存在，则输出茶包的使用顺序，G表示绿茶包，B表示黑茶包； 如果不存在，则输出NO; 输入数据 n, k, a and b (1 ≤ k ≤ n ≤ 1e5, 0 ≤ a, b ≤ n)

Examples input 5 1 3 2 output GBGBG input 7 2 2 5 output BBGBGBB input 4 3 4 0 output NO

题目解析： 题目的要求是分配茶包。 容易想到这样的贪心：每天优先使用多的茶包，当使用了k次之后，就用一次少的茶包，直到茶叶包一样多，之后可以采取交替的方式。 这样的实现方案会比较复杂，首先需要每天判断一次a、b的大小，然后还要记录当前茶包是否连续使用了k次。 我们可以用另外一种贪心：当a>b的时候，我们直接连续使用min(k, a - b)个b茶包。 容易知道，当a-b<k时，剩下的茶包数量相等，交替使用即可； 如果使用的是茶包k时，证明a比b多超过k，这时先使用k个a不会影响最后的结果。

这个题的思路很多，选择一个较好实现的。

5.Numbers Exchange

题目链接 题目大意： 小明有n张卡片，每张卡片上有一个数字a[i]; 小红有m张卡片，卡片上的数字分别从1~m； 现在小明可以和小红交换卡片，每次用他的一张卡片去交换小红的一张卡片； 要求：小明所有奇数的卡片和偶数的卡片一样多，并且每一张的数字各不相同。 输入数据： n and m (2 ≤ n ≤ 2·1e5, 1 ≤ m ≤ 1e9) a1, a2, ..., an (1 ≤ ai ≤ 1e9)

如果可以达到，先输出最小的交换次数； 然后输出n个数字b[i], b[i]=a[i]表示这张卡片没变，b[i]!=a[i]，表示小明用第i张卡片去交换了小红的第b[i]张卡片； 如果不能达到，输出-1；

Examples input 6 2 5 6 7 9 4 5 output 1 5 6 7 9 4 2 input 8 6 7 7 7 7 8 8 8 8 output 6 7 2 4 6 8 1 3 5 input 4 1 4 2 1 10 output -1

题目解析： 从结果来反推。 假设小明最后能达成条件，那么需要n/2张奇数和偶数的卡片，即是需要各不相同的奇数和偶数各n/2; 即是小明和小红的卡片去重后，奇数和偶数的数量都要大于等于n/2;

容易知道，小明需要把去重时的卡片、大于n/2张的奇偶卡片去和小红交换； 那么对于一张奇数卡片a[i]，假设当前奇数卡片剩下sum1张，如果还有多余的卡片a[i]或者sum1>n/2 || (sum1==n/2 && 剩余卡片>1)那么这张卡需要交换； 当所有卡片处理完之后，判断奇数、偶数卡片是否等于n/2即可。

思考?： 代码比较长，所以在提交之后查看别人的解法。 其实不需要去重之后，再来遍历卡片，判断是否应该交换； 在一开始输入的时候，如果一个卡片是重复的（之前已经出现过），或者当前类型（奇偶数）剩余的卡片已经�大于等于n/2，这张卡片就是多余的，可以加入交换queue里面； 输入完成时，会有一个交换queue，这个queue就是需要交换的卡片； 再按照奇偶数卡片的数量，去和小红交换，最后得到奇偶卡片的数量，再判断。

总结

五道题都是想法题。 第3、4、5题要求思路清晰，稍有遗漏，就会遇到错误，是很不错的题目。

手机附： 实际开发中，最常见的就是“贪心”，“时间与空间互换”，“减少重复计算”，“lazy加载”等思想，这些想法都是算法的一个延伸。 最近做的一个功能，涉及到环形缓冲区的优化和二进制流处理，每次处理仅有12ms的时间。我觉得曾经算法练习能很好帮我解决问题，过去类似的思考都转化为现在的灵光。