1 条题解
-
0
题目分析
20 分
暴力 dfs 即可。
考虑在二进制上解决该问题。
因为最初只有一块蛋糕,那么这个问题就变得非常简单。
从高位向低位考虑,如果当前 这一位为 ,那么就选择最小的蛋糕一直切,直到切出了当前二进制位对应大小的蛋糕。
正解
首先无解是好判断的,所有蛋糕的和小于 就无解,否则可以把蛋糕都切成大小为 。
考虑到 很大,而且 有一个 的幂次的限制,不如在二进制下考虑问题。
因为把高位的 往下一位拆会有 的代价,而低位的 向高位的合成是免费的,于是从低位向高位贪心。
假设现在贪心到了第 位( 的二进制表示下第 位为 ),如果当前存在一块蛋糕大小为 ,那么直接用了,剩下的蛋糕向高位合成(两块大小为 的蛋糕可以当成一块大小为 的蛋糕),保证蛋糕的充分利用。
如果不存在,怎么办呢?考虑将大的蛋糕往下面拆,找到最小的一块比 大的蛋糕,往下一直切,知道切出一块大小为 的蛋糕即可。
这样贪心的正确性显然,时间复杂度 。
- 1
信息
- ID
- 62
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者