binary search

第 255 场周赛 5853. 从子集的和还原数组

Rank 205，手速慢了。最后一题不会做。。。

Desciption

存在一个未知数组需要你进行还原，给你一个整数 n 表示该数组的长度。另给你一个数组 sums ，由未知数组中全部 2n 个 子集的和组成（子集中的元素没有特定的顺序）。

返回一个长度为 n 的数组 ans 表示还原得到的未知数组。如果存在 多种答案，只需返回其中 任意一个。

如果可以由数组 arr 删除部分元素（也可能不删除或全删除）得到数组 sub ，那么数组 sub 就是数组 arr 的一个 子集。sub 的元素之和就是 arr 的一个 子集的和。一个空数组的元素之和为 0 。

注意： 生成的测试用例将保证至少存在一个正确答案

1 <= n <= 15
sums.length == 2^n
-10^4 <= sums[i] <= 10^4

示例：

输入：n = 4, sums = [0,0,5,5,4,-1,4,9,9,-1,4,3,4,8,3,8]
输出：[0,-1,4,5]
解释：[0,-1,4,5] 能够满足给出的子集的和。

阅读全文 >>

第 226 场周赛 5667. 你能在你最喜欢的那天吃到你最喜欢的糖果吗？

差2分钟做出来最后一题，好气！！rank 767

Desciption

有 n 类糖果，下标从 0 开始的正整数数组 candiesCount ，candiesCount[i] 表示第 i 类糖果的数目。 有一个询问数组 queries ，其中 queries[i] = [favoriteTypei, favoriteDayi, dailyCapi] 表示一个询问：在每天吃 不超过 dailyCapi 颗糖果的前提下，你可以在第 favoriteDayi 天吃到第 favoriteTypei 类糖果吗？

你按照如下规则进行一场游戏：

• 你从第 0 天开始吃糖果
• 你在吃完 所有 第 i - 1 类糖果之前，不能 吃任何一颗第 i 类糖果。
• 在吃完所有糖果之前，你必须每天 至少 吃一颗 糖果。

构造一个答案数组 answer 返回，answer[i] 为 true 表示第 i 个询问可以实现，为 false 表示不可以实现

输入：candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]]
输出：[true,false,true]

输入：candiesCount = [5,2,6,4,1], queries = [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]]
输出：[false,true,true,false,false]

阅读全文 >>

第 225 场周赛 5664. 放置盒子

最后一题没时间做，好菜好气。rank 567

Desciption

有一个立方体房间，其长度、宽度和高度都等于 n 个单位。请你在房间里放置 n 个盒子，每个盒子都是一个单位边长的立方体。放置规则如下：

• 你可以把盒子放在地板上的任何地方。
• 如果盒子 x 需要放置在盒子 y 的顶部，那么盒子 y 竖直的四个侧面都 必须 与另一个盒子或墙相邻。 给你一个整数 n ，返回接触地面的盒子的 最少 可能数量。 示例：

输入: n = 3
输出: 3

输入: n = 4
输出: 3

输入: n = 10
输出: 6

阅读全文 >>