1 条题解
-
0
题目分析
题目中有一个非常重要的性质:编号为 的石头比所有编号小于 的石头加起来的重量还要重。意思就是无论在所有编号小于 的石头中怎么选,得到的重量之和都不如直接选第 块石头来得重。
这其实与二进制有相同的性质:对于二进制的第 位,一定比 位之和更大。也就是说,把所有石头按编号从小到大排列后,可接受重量的第 小值(从 开始编号),恰好就是 的二进制表示中为 的那些位所对应的石头重量之和。
于是做法就很直接了:把 减 后,考察它在二进制下每一位是否为 ,若第 位为 ,就把第 块石头的重量累加进答案。若 的二进制位数超过了 ,说明这个组合不可能达成,输出 。
需要注意 最大可达 ,需要用 64 位整数存储。
- 1
信息
- ID
- 45
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者