Div.2 CF 1105A题（位运算，贪心）

题目链接https://codeforces.com/contest/2240/problem/A题目大意给你两个数n和k。你要构造k 个非负整数也就是 a₁, a₂, …, aₖ要求这 k 个数的总和不超过 n所有数的二进制中1 的个数加起来尽可能多。你只需要输出这个最大的中1的总个数。题目思路因为每个数贡献的“得分”都是 1所以优先选最小的1、2、4、8……这样能用有限的总和n买到最多的个数。代码如下#include bits/stdc.h using namespace std; //#define int long long #define endl \n void solve() { int n, k; cin n k; int ans 0; // 总共能买到多少个 1 int coin 1; // 当前买的硬币面值1, 2, 4, 8, ... while (coin n) { int canBuy n / coin; // 当前剩余钱最多能买多少个 coin int buy min(canBuy, k); // 但每个盒子最多只能买一个 ans buy; // 每买一个 coin 就得到 1 个 1 n - buy * coin; // 花掉钱 coin * 2; // 买下一个面值 } cout ans endl; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cinT; while (T--) { solve(); } return 0; }