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

前言

四道题，分别锻炼哈希、贪心、贪心+排序、二分四个能力。 第一题较为简单，后续的题目都需要一定的基础。 贪心是最基础的能力，codeforce有专门的 Tag用以描述，叫做greedy； 二分是常用的一种降低时间复杂度方法，前提的要求是单调性； 哈希和排序是工程中常见的处理，前者用于映射，后者用于数据有序化。 这四个能力也多用于面试的算法题，因为其属于基础能力。

正文

1.Santa Claus and Keyboard Check

题目链接 题目大意： 小明把键盘的键都卸下来清洗，在装回去后，发现有些键装错了。 他看着键盘，打出一个字符串str，在屏幕显示出来一个字符串str'; 现在他可以选择任意两个键，交换它们的位置，但是每个键只能交换一次；

问，小明是否能复原正确的键盘？ 如果可以，先输出交换次数，接下来每行输出每次交换的字母；（顺序无关） 如果不可以，直接输出-1。

输入数据： str长度不超过1000；

Examples input helloworld ehoolwlroz output 3 h e l o d z input merrychristmas christmasmerry output -1

题目解析： 题目有个很重要的条件，每个键只能使用一次。 那么每次当遇到字符不同的时候，这两个字符就必须交换；如果这个字符已经交换过，那么无解。

实现逻辑，可以用一个简单字符hash来实现，对str的字符，每次先判断是有hash字符，如果有则转成hash后的符； 如果没有，添加hash[c]=c; 保证下次再遇到不会出错； 然后进行判断，如果hash后的字符和str'上的不对应，则无解；

2.Santa Claus and Robot

题目链接 题目大意： 有一个机器人，在一个网格的网格线上行走，每次有L/R/U/D四个方向； 当机器人从点p1走到点p2时，它会走最短的路径。 如果有3个点p1、p2、p3，机器人会按照最短的路径走向p1点，到达后再走向p2点，再到p3点； 现在假设机器人在原点，已知机器人走的序列（长度为n），求最少有几个点，可以满足机器人走的序列。

输入数据： n (1 ≤ n ≤ 2·105)

Examples input 6 RRULDD

output 2 input 26 RRRULURURUULULLLDLDDRDRDLD output 7

题目解析： 看似很难，仔细分析一下，只要找到两点之间路径的规律即可。 当出现过R之后，本次路径，就不允许再出现L，同理L、U、D; 这样，R、L之间算一条路径，U、D之间算一条路径，加起来就是需要的最小点数。

3.Santa Claus and a Palindrome

题目链接 题目大意： k个字符串，长度均为n； 每个字符串有一个权值a[i]； 现在可以从k个字符串中，选择若干个字符串拼成一个新的回文串str，要求每个字符串只能用一次，并且不能改变原有字符串的字符排列顺序； str的权值为所有拼成的串的权值和，求str的最大权值。 （注意，空串也是回文串，所有str的最大权值不小于0）

输入数据： 1 ≤ k, n ≤ 100 000; n·k  ≤ 100 000 - 10 000 ≤ a[i] ≤ 10 000

Examples input 7 3 abb 2 aaa -3 bba -1 zyz -4 abb 5 aaa 7 xyx 4 output 12 样例解释：最后的结果是abbaaaxyxaaabba，组合第5, 2, 7, 6 和 3字符串。

题目解析： 每个字符串分两种，第一种是自身为回文，第二种是自身不为回文。 自身为回文串有两种选择，放在中心点（单独一个）和不放在中心点（两两配对分在左右）； 自身不为回文串的字符串str，可以和str的reverse组合回文串；（比如abc和cba） 我们把字符串相同的放到同一个桶，把桶按照字符串是否为回文分成两类。 对于非回文串str，每次从str的桶里找一个最大的key值x，再从reverse(str)的桶里找一个最大的key值y，只要x+y>0，那么就组成一个匹配； 对于回文串paliStr，每次从paliStr的桶里找key值最大的两个x和y，如果x+y>0，那么就组成一个匹配； 这里有个trick：因为paliStr还可以单独放在中间，如果paliStr的两个权值是-3和5，那么选中-3其实是不划算的。 但是如果只选择x>0&&y>0的话，假设有多个-3和5的组合，就会失去-3+5=2的额外收益。 抉择是根源是在于paliStr可以选择放在中间！但是中间其实只能有一个字符串。 于是可以采取额外补偿的方式，我们还是采用x+y>0的选择，但是保留一个addition的收益，类似-3和5的组合，addition的收益是3； 同理，如果只剩下一个回文串，那么addition的收益是该回文串。 最后计算所有的收益和+addition收益得到答案。

思考?： 更好理解addition的方式，是把组合看成单体的，比如说pair(-3, 5), pair(2, 3)；把剩下的单个，也视为单体； 然后从所有的单体中选择一个，放入中间的收益。

4.Santa Claus and Tangerines

题目链接 题目大意： 给出n个数字a[i]，要分给k个人； 数字a[i]可以平分，如果是奇数，那么会分成a[i]/2 和 a[i]/2 + 1; 每个人只能分得一个数字，问所有人中最小的数字的最大值是多少？ 如果不够分，那么输出-1；

输入数据： n and k (1 ≤ n ≤ 1e6, 1 ≤ k ≤ 2·1e9) 1 ≤ a[i] ≤ 1e7

Examples input 3 2 5 9 3 output 5 input 2 3 1 1 output -1

题目解析： 分出k个数，保证最小值尽可能大； 第一想法是二分答案，假设最后的结果是ans，对于数字x，while(x/2>=ans)，对数字x进行平分； 假设num[x]表示数字x的数量，如果x/2>=ans，那么有num[x/2] += num[x], num[x - x/2] += num[x]; 最后再统计所有数字比ans大的数字数量，判断是否大于k； 复杂度为二分复杂度log(1e7) * 枚举平分复杂度(1e7) =24*1e7=2.4e8的复杂度； 因为题目给的时限为2s，勉强可以完成；

思考?： 另一种更优雅的方案。 以数字21为例，如果ans∈[11, 21]这一区间，>ans的数字只有一个； 如果ans=10时，就能算两个数字；（因为21可以拆分为10+11） 数字x，可以切分为数字较小的部分x/2和数字较大的部分(x-x/2)，我们用a[x]来表示数字x的个数，b[x]表示当x拆分时(x-x/2)的数量； 当ans>(x-x/2)时，x的拆分没有额外收益； 当ans<=x/2时，x的拆分相当于多出来一个数字a[x/2]； 于是有： a[x/2] += a[x]+b[x]; b[x-x/2] += a[x]+b[x]; 核心代码很短，如下：

    for (lld i = maxAns; i > 0; --i) {
        total += a[i];
        if (total >= k) {
            cout << i << endl;
            return 0;
        }
        else {
            a[i / 2] += a[i] + b[i]; 
            b[i - i / 2] += a[i] + b[i];  
        }
    }

总结

基础能力在做一线开发的时候极为重要，往往决定了综合能力的天花板。 实际开发中的各种性能优化，功能系统的时间空间复杂度分析，都是基于基本的算法能力。 算法是编程能力提升的必要条件，做题只是学算法的一种实践手段。 而在业余时间越来越少的现在，做题占用的是我的娱乐时间和学习时间。如果一直停留在重复做类似题的境界，对我的能力提升微乎其微。 所以我现在在做的事情是尝试用规范的方式去解决、思考问题，然后把这个过程用文字描述出来。在保持思考习惯的同时，提升描述能力和锻炼耐力。