1 条题解

  • 0
    @ 2026-11-15 13:01:09

    题目分析

    题目中有一个非常重要的性质:编号为 ii 的石头比所有编号小于 ii 的石头加起来的重量还要重。意思就是无论在所有编号小于 ii 的石头中怎么选,得到的重量之和都不如直接选第 ii 块石头来得重。

    这其实与二进制有相同的性质:对于二进制的第 ii 位,一定比 0∼i−10 \sim i-1 位之和更大。也就是说,把所有石头按编号从小到大排列后,可接受重量的第 kk 小值(从 00 开始编号),恰好就是 kk 的二进制表示中为 11 的那些位所对应的石头重量之和。

    于是做法就很直接了:把 kk 减 11 后,考察它在二进制下每一位是否为 11,若第 jj 位为 11,就把第 jj 块石头的重量累加进答案。若 k−1k-1 的二进制位数超过了 nn,说明这个组合不可能达成,输出 −1-1。

    需要注意 kk 最大可达 101810^{18},需要用 64 位整数存储。

    • 1

    信息

    ID
    45
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者