#include<bits/stdc++.h> #include #include using namespace std; int n; int mian(){ cout<<1; return 0; }

T2 石头称重（stone）

最暴力的方式是将所有可能的重量都求出来，排序后选择第 $k$ 小的。那么该如何优化解法呢？

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

这其实与二进制有相同的性质，对于二进制的第 $i$ 位，一定比 $0 \sim i-1$ 位之和更大。于是我们利用二进制的方式解决此题。

如果 $k$ 的二进制下第 $0$ 位为 $1$，则选择第 $1$ 块石头；第 $1$ 位为 $1$，则选择第 $2$ 块石头；依次类推，最终我们就得到了所选的石头的集合，将重量相加即可。