P1582 倒水【洛谷算法习题】

P1582 倒水网页链接P1582 倒水题目描述一天CC 买了N NN个容量可以认为是无限大的瓶子开始时每个瓶子里有1 11升水。接着 CC 发现瓶子实在太多了于是他决定保留不超过K KK个瓶子。每次他选择两个当前含水量相同的瓶子把一个瓶子的水全部倒进另一个里然后把空瓶丢弃。不能丢弃有水的瓶子显然在某些情况下 CC 无法达到目标比如N 3 N 3N3、K 1 K 1K1。此时 CC 会重新买一些新的瓶子新瓶子容量无限开始时有1 11升水以达到目标。现在 CC 想知道最少需要买多少新瓶子才能达到目标呢输入格式一行两个正整数N , K N, KN,K1 ≤ N ≤ 2 × 10 9 1 \le N \le 2 \times 10^91≤N≤2×109K ≤ 1000 K \le 1000K≤1000。输出格式一个非负整数表示最少需要买多少新瓶子。输入输出样例 #1输入 #13 1输出 #11输入输出样例 #2输入 #213 2输出 #23输入输出样例 #3输入 #31000000 5输出 #315808解题思路本题将瓶子的合并过程抽象为二进制数的加法进位核心结论是最终剩余的瓶子数等于当前总水量瓶子数的二进制表示中1的个数。目标是最少添加多少个新瓶子每个带1 11升水使得最终瓶子数不超过K KK这等价于求最小的非负整数a aa使popcount ⁡ ( N a ) ≤ K \operatorname{popcount}(N a) \le Kpopcount(Na)≤K。1. 问题等价转化合并规则每次选择两个水量相同的瓶子合并相当于两个相同的“水量单位”相加产生一个水量翻倍的瓶子。这与二进制加法中“两个1 11相加得0 00并进位”完全一致。水量与二进制若将所有瓶子的水量用二进制表示每个1 11升水相当于二进制最低位的1 11。任意时刻的总水量即初始瓶子数N NN保持不变。经过一系列合并后剩下的瓶子水量必然各不相同且对应N NN的二进制表示中为1 11的那些位。因此剩余瓶子数 N NN的二进制中1 11的个数。添加新瓶子每买一个装有1 11升水的新瓶子相当于总水量N NN加1 11。我们要通过增加N NN添加瓶子使得popcount ⁡ ( N ) ≤ K \operatorname{popcount}(N) \le Kpopcount(N)≤K且增加量最小。目标求最小的非负整数a aa满足popcount ⁡ ( N a ) ≤ K \operatorname{popcount}(N a) \le Kpopcount(Na)≤K。2. 算法实现贪心进位消除低位1根据二进制特性要减少1 11的个数最直接的方法是将最低位的1 11不断进位。具体步骤初始化增量a 0 a 0a0。当popcount ⁡ ( N ) K \operatorname{popcount}(N) Kpopcount(N)K时取出N NN的最低有效位lowbit N -N。令a ← a lowbit a \gets a \text{lowbit}a←alowbitN ← N lowbit N \gets N \text{lowbit}N←Nlowbit。循环结束后a aa即为最少需要购买的新瓶子数。正确性解释N lowbit会将最低的一组连续1 11全部变为0 00并向上产生一个进位这通常会使总1 11的个数减少或保持不变但如果连续1 11段很长总体仍趋向减少。按最低位开始逐次进位可以保证每次增加量尽可能小从而最终增量最小。3. 复杂度分析时间复杂度每次操作至少消除一个二进制1 11最多执行popcount ⁡ ( N ) \operatorname{popcount}(N)popcount(N)次而N ≤ 2 × 10 9 N \le 2 \times 10^9N≤2×109二进制位数不超过31 3131循环次数极少。空间复杂度O ( 1 ) O(1)O(1)仅使用几个变量。总结巧妙地利用二进制表示模拟瓶子合并过程将“保留不超过K KK个瓶子”转化为“使N NN的二进制中1 11的个数不超过K KK”。通过不断将最低位1 11进位即加上lowbit用最少的增量达到目标。整个过程只用位运算高效简洁。代码简要说明读入N , K N, KN,K初始化累加器a 0 a 0a0。使用__builtin_popcountll(n)统计当前N NN的二进制中1 11的个数当大于K KK时循环计算lowbit n -n。a lowbitn lowbit。输出a aa。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,k,a0;scanf(%lld%lld,n,k);while(__builtin_popcountll(n)k){an-n;nn-n;}printf(%lld,a);return0;}