leetcode 周赛 492，排名31

零、背景

这次比赛非常简单，30 分钟之内就写完了，可惜第二题错了一次，没进入前 25 名。

本场题型概览如下。
A 题：最小值。
B 题：前缀和。
C 题：分类贪心。
D 题：前缀和+递归。

最终排名：31。
代码仓库：详见 https://github.com/tiankonguse/leetcode-solutions。

一、容量最小的箱子

题意：求大于等于 X 的最小值，多个时返回第一个。

思路：记录下当前最小值，遇到满足的更小的，则更新最小值。

二、找出最小平衡下标

题意：找一个下标，使得前缀和等于后缀积。

思路：预处理前缀和，从后到前计算后缀积，比大小。

小技巧1：后缀积大于前缀和时，直接结束循环。
小技巧2：使用__int128_t避免乘积溢出。
小技巧3：先使用double粗略判断大小，再使用long long精确判断大小。

三、将一个字符串排序的最小操作次数

题意：给一个字符串，每次可以选择一个子串进行排序，问最少需要多少次操作可以使得字符串有序。

思路：贪心

前缀子串定义：长度为n-1的前缀字符串，即不包含最后一个字符的子串。
后缀子串定义：长度为n-1的后缀字符串，即不包含第一个字符的子串。

如果已经有序，直接返回 0。
如果第一个字符就是最小值，后缀子串排序即可，直接返回 1。
如果最后一个字符就是最大值，前缀子串排序即可，直接返回 1。
否则最小值或者最大值在中间，前缀子串与后缀子串分别排序，直接返回 2。

特殊情况1：最值不在中间，即最小值在最后一个位置，最大值在第一个位置，中间不存在最值。
这时候，需要先选择后缀或者前缀排序一次，把最值调整到中间，然后再排序两次得到有序字符串。
答案为 3。

特殊情况2：字符串长度为 2，且不是有序。
此时，永远得不到答案。
返回 -1。

四、划分二进制字符串的最小费用

题意：给一个二进制字符串，每个子串有一个代价，长度是偶数时可以选择拆分为两个等长的子串，代价是两个子串的代价之和。问最小代价。
对于长度为 L 的二进制串中 1 的个数为 X 的代价定义为：X 为 0 时代价为 A，否则代价为 L * X * B。

思路：递归

一开始可以预处理前缀和，从而可以快速计算出每个子串的代价。
拆分是可选择的，那就分别计算出两个答案，取最小值即可。

拆分不存在重复子问题，所以不需要缓存。
复杂度：O(n)

五、最后

这次比赛比较简单，第二题乘法会越界，需要使用 __int128_t。
第三题贪心的分类情况比较多，不注意会遗漏。
第四题递归比较简单，不需要缓存。

《完》。

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号 ID：tiankonguse-code