leetcode 第 350 场算法比赛

零、背景

这次比赛最后一题有点难，做完后还以为排名会到四五百名，没想到进入前百名了。

一、总行驶距离

题意：卡车有主副两个油箱，开车只能使用主油箱，主油箱用掉 5 升油时副邮箱有1升油可以加到主邮箱。
问最终可以使用多少油。

思路1：模拟减五，一点点加油，复杂度O(n)
思路2：模拟除五，批量加油，复杂度O(log(n))

二、找出分区值

题意：给一个数组，求拆分为两个数组，使得第一个数组的最大值与第二个数组的最小值的差值最小。

思路：

第一个数组是求最大值，显然所有小于最大值的元素都可以在第一个数组，不影响答案。
同理，第二个数组是求最小值，则所有大于最小值的元素可以在第二个数组。

所以两个数组的特征就变为第一个的最大值小于第二个数组的最小值。
即原数组排序后，找一个分割线，左半部是第一个数组，右半部是第二个数组。

枚举所有分割线，去最小差值即可。

三、特别的排列

题意：给一个元素值互补相等的数组，求数组的排列，使得数组相邻元素满足整除关系。
问满足要求的排列的个数。

思路：数组长度为 14，典型的二进制枚举题。

假设当前排列的前缀已满足条件，最后一个元素是 x。
则剩余元素组成满足要求的排列只与 x 有关。
即可以定义状态为 f(x, mask)，含义是上一个元素是 x，剩余元素为 mask 的答案个数。

状态转移方程：枚举 mask，找到所有满足整除关系的值，求子状态。

复杂度：O(n^2 * 2^n)

四、给墙壁刷油漆

题意：给一个数组，值分别付费工人做一个任务的价钱与时间。
现在有一个免费工人，可以用 1 单位时间完成任意任务，但是免费工人必须与付费工人同时干活。 问怎么分工，才能使得总花销最低。

基础推导：

假设付费工人选择了 useNum 个任务，对应的总价钱是 useSumCost，对应的时间是 useSumTime。
则免费工人可以做完 useSumTime 个任务。
此时可以得到方程：useNum + useSumTime >= n

而 useSumTime 等于 sum(useOneTime)。

故方程可以转化为

useNum + useSumTime >= n
useNum + sum(useOneTime) >= n
sum(useOneTime + 1) >= n

方程推导到这里，可以得出一个结论：求选择若干任务，使得选择的任务的时间加一之和不小于n时的最小代价。

面对这个问题，有两种方法。

方法一：二分代价，使用0/1背包算法判断是否满足要求。
但是费用的空间是 10^6，空间复杂度太大。

方法二：动态规划。
定义状态：f(k, sumTime) 前 k 个物品, 时间大于等于 sumTime 的最小费用。
状态转移方程也很简单，对于最后一个物品选择与不选择。

当然，选择不选择，其实就是 0/1背包的本质，所以可以理解为使用0/1背包可以直接求出答案。
复杂度：O(501^2)

五、最后

这次比赛最后一题很有挑战，我是没有套路0/1背包模版，而是使用朴素的动态规划做出来的。

最后一题你是怎么做的呢？

《完》

-EOF-

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