这次还行
https://i.imgur.com/fSiFtLV.png
1. Take Gifts From the Richest Pile
用一个 heap 来不断取出最大值
不过因为 n, k <= 1000
所以其实可以不需要 heap 就是了
没看到 floor 在那边找到底有没有一定是整数
第一题就花了八分钟 = =
2. Count Vowel Strings in Ranges
建一个 prefix sum 阵列即可
3. House Robber IV
我用 binary search 解的
答案能够 <= v 的条件是：
在只选那些 <= v 的人时能不能选出 >= k 个
不知道有没有线性解就是了
4. Rearranging Fruits
首先每个数字的出现次数必须是偶数否则不可能
接着对各自阵列找出多出来的部份
假如多出来的部份分别是
A = a_1, a_2, ..., a_k
B = b_1, b_2, ..., b_k
则对于 A 而言，我们最后要让个数一样
所以最终一定是以下这种形式
换出 a_1, a_2...，a_k
换进 b_1, b_2, ..., b_k
换出及换进相等次数的 t_1, t_2, ...
对于固定好换出 (a_1, ..., t_1, t_2,...) 换进 (b_1, ..., t_1, t_2, ...)
而言，假如有 n 个数
最佳解一定是挑比较小的 n/2 个数分别配上比较大的 n/2 个数
因此最后的最佳解就会是
a_1, a_2, ..., a_k, b_1, b_2, ..., b_k
中最小的 k 个数，但可以用两次 basket1 及 basket2 中的最小值代替