题目

题目描述 小明买了N个容积可以是无穷大的杯子，刚开始的时候每个杯子里有1升水， 接着小明发现杯子实在太多了，于是他决定保留不超过K个杯子。每次他选择两 个当前含水量相等的杯子，把一个杯子的水全部倒进另一个里，然后把空瓶丢弃。
（不能丢弃有水的杯子） 显然在有些情况下小明无法达到他的目标，比如N=3，K=1。此时小明会重
新买一些新的杯子（新杯子容积无限，开始时有1升水），以达到目标。 现在小明想知道，最少需要买多少个新杯子才能达到目标呢？ 输入 一行两个正整数，N，K（1≤N≤1000000000，K≤1000）。 输出 一个非负整数，表示最少需要买多少新杯子。 样例输入 1000000 5 样例输出 15808 提示 【数据范围】
对于50%的数据，N≤10000000； 对于100%的数据如题目。

分析

　　声明：由于我实在是太蔡了，所以考试的时候根本没想到正解……

　　后来推样例的时候，我才发现杯子内的水从1到2再到4的过程很像2进制运算，且本题数据极大，O(n)都不行，所以CJX告诉我，要么是贪心，要么是数论，要么是贪心+数论。

　　所以每一个杯子里的水量都是2^x（x为非负整数），进而我们知道每2^y个水量为1杯子可以变成1个杯子（这一个杯子里的水量为2^y）。

　　为了使新添的杯子数量最少，所以每次都要让y最大，故使用贪心。

代码

#include<bits/stdc++.h> using namespace std; long long n,k,a,x=1,sum=1; int main() {scanf("%lld%lld",&n,&k);if(k>=n){putchar('0');exit(0);}while(sum<=n) sum<<=1a=sum>>1;while(x<k){while(a>n) a>>=1;x++;n-=a;}sum=1;while(sum<=n) sum<<=1;//计算需要用几个水量为1杯子才能将剩下的所有杯子变成一个杯子。 printf("%lld",sum-n);return 0; }

转载于:https://www.cnblogs.com/DARTH-VADER-EMPIRE/p/11363039.html

总结

以上是生活随笔为你收集整理的杯子的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。