第一题：
直接开一个26长度的结构体数组（结构体有队伍名字'a-z'，得分）。然后读入字符串，按照题意计算对应的字母的得分，累加到对应数组位置上，比如'a'的对应位置是0，z是25。最后按照得分第一关键字从高到低，名字第二关键字从低到高排序就可以了。
第二题：
1.假如a说有x个人和他一样颜色，那么a的颜色至多能容纳（x+1)个人。
2.假如a说x，b说y，那么a和b的颜色一定不一样，为什么呢？举个例子，有两种颜色分别为1,2。假设分布为 1 1 2 2 2 ，其中a为1颜***为2颜色，那么a会说1，b会说2。假设b为1颜色，那么b也会说1。
3.前两点得出的结论就是说，其实每个人相当于买了一栋楼，楼里的房间个数为（x+1)，自己先占了一间，然后这栋楼还可以住和他说一样的数字——也就是x的人。注满即止。如果有(x+2）个人说了x，那么就得新买一栋楼。
4.所以答案很显然了，直接求出说x的人数，然后求这些说x的人数至少得住几栋楼，那么就是 ceil (cnt(x) / (x+1))。 其中ceil是向上取整。
5.用4的方法对每个x累加即可。
第三题：
贪心是错的，暴力回溯会超时，正解是dp。
dp的话其实也有几种思路，其中一种就是评论区老哥发的leetcode上的一道类似题的官方解法https://leetcode-cn.com/problems/freedom-trail/。感兴趣的自己去看，他的复杂度是O（n^2m)的。
在这里讲下我的做法吧，复杂度是O(nm)的。
首先：用start表示游标起始位置，n表示字符数组长度，m表示匹配串长度。a表示字符数组，b表示匹配串。
1.前面的表示以及dp转移其实和leetcode题解是相似的。
2.dp[i][j]表示现在游标指在a的i位置，匹配了b的j个字符，所用的最少的移动次数。
3.初始化dp[i][j]=INF(也就是正无穷，1e7以上就行，我用的1e8）
4.那么dp[start][0] = 0。其余的dp[i][0] = min(abs(i-start),n-abs(i-start) ) 也就是向左或者向右取最小的步数。
5.转移方程：
(1) dp[i][j] = dp[i][j-1] if a[i] == b[j] (也就是不用移动游标了，因为当前的i就可以匹配了) (2) dp[i][j] = min(dp[i][j],dp[i+1][j]) 这个i和i+1记得取模，这里就不写了 (3) dp[i][j] = min(dp[i][j],dp[i-1][j]) 这个i和i-1记得取模，这里就不写了6.过程：
- 枚举j
- 遍历a，如果a[i]==b[j]，那么用(1)号方程转移
- 从后往前遍历两轮用(2)号方程转移
- 从前往后遍历两轮用(3)号方程转移
- 最后答案就是min dp[i][m] (i in 0 to n-1)
全部评论
(13) 回帖