leetcode 第 442 场算法比赛

零、背景

这次比赛题目不难，但是频繁敲错，导致全部做完时排名比较靠后了。

A: 数学公式
B: bitset + 并查集
C: 贪心
D: 数学公式

排名：200+
代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest

一、船上可以装载的最大集装箱数量

题意：船最多承载个 N 集装箱和最大重量 W，每个集装箱重 w，问最多可以装载多少集装箱。

思路：数学公式

计算最大重量的集装箱个数，然后与 N 取最小值即可。

复杂度：O(1)

二、属性图

题意：有 n 个点，每个点有 m 个属性，如果两个点的属性交集个数大于等于 k，那么两个点之间有一条边。
问图中有多少个连通分量。

思路：bitset + 并查集

预处理每个点，属性储存在 bitset 中。
然后枚举所有点对，判断 bitset 交集是否大于等于 k, 如果大于等于 k，则代表两个点之间存在边，合并两个点的并查集。
最后统计并查集根是自己的个数即可。

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

三、酿造药水需要的最少总时间

题意：有 m 个药水需要按顺序制造，每个药水由 n 个工人按顺序酿造。
每个工人同一时间只能酿造一个药水，而且对于同一个药水上一个工人完成后，下一个人需要马上开始，即中间不能有等待时间。
问所有药水都完成的最短时间。

思路：贪心

对于同一个药水，工人需要按顺序制造，且中间不能间隔。
所以对于同一个药水，制造时间是固定的，就是这个药水每个工人制造时间之和。

前一个药水制造出来后，对于下一个药水，需要找到一个开始制造时间，使得每个工人满足两个条件。

条件1：每个工人的开始时间大于等于这个工人前一个药水的结束时间，也等价于下个工人前一个药水的开始时间（同一时间只制造一个）。
条件2：每个工人的结束时间大于等于下个工人前一个药水的结束时间（下个工人不能等待）。

可以发现，如果药水的开始时间是无效大的，两个条件显然都满足。
所以我们贪心找到一个开始时间，如果不满足了，就延后开始时间，从而使得所有工人都满足两个条件。

另外，可以发现，我们只关心两个药水制造时间的相对顺序，不关心前一个药水第一个工人的开始时间。
故在计算下一个药水的开始时间时，只需要考虑上一个药水每个工人消耗多长时间即可，不需要关心具体什么时间开始制造的。

方法1：二分

时间延后一旦满足，后面的都满足，故可以二分找到最小的延后时间。
复杂度：O(n^2 * log(n))

方法2：贪心

按题意对每个工人进行贪心与微调。
先贪心计算第一个工人的开始时间，然后判断下个工人是否满足，缺多少时间就补多少时间。

复杂度：O(n^2)

PS：比赛的时候想复杂了，我是倒着处理每个工人的，然后有个地方手滑敲错了，导致调试好久。

四、使数组元素都变为零的最少操作次数

题意：给一个区间 [l,r], 代表值为 l,l+1,...,r 的数组。
现在每次操作可以选择两个元素，值修改为 v/4。
问最少操作多少次，可以使得数组所有元素都变为0。

思路：数学公式

首先可以证明，每次操作2个元素的总次数 与 每次操作1个元素的总次数的一半，剩余1个则向上取整。
故问题转化为了所有数组元素都变为0的最小操作次数。

由此可以推导出一个公式：

f(l,r) = F(r) - F(l-1);

分析一个连续区间，可以发现，每次操作，区间的值会降低为原来的 1/4，重复元素翻 4 倍， 故可以推导出下面的公式。

F(r) = 4 * F(r/4) + r;

当然，这个公式只对中间的区间有效，对于边界的区间，需要单独处理。

F(r) = r // 所有的数字除以 4
  + 4 * F(r/4 - 1) // 中间的 4 个一组，递归计算答案
  + Count(r) * log(r, 4); // 统计边界个数，单独暴力不断除4计算答案

可以发现，这是一个递归的公式，由于递归层数是 log(n)，所以复杂度是 O(log(n))。

PS1: 比赛的时候，我看出向上取整了，调试半天。
PS2：比赛的时候是直接计算 f(l,r)的，稍微复杂一些。

五、最后

这次比赛后三题都上难度了，第二题并查集、第三题二分或者贪心，第四题数学公式，都不简单的。

《完》

-EOF-

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