题目描述
一天，CC买了N个容量可以认为是无限大的瓶子，开始时每个瓶子里有1升水。接着~~CC发现瓶子实在太多了，于是他决定保留不超过K个瓶子。每次他选择两个当前含水量相同的瓶子，把一个瓶子的水全部倒进另一个里，然后把空瓶丢弃。(不能丢弃有水的瓶子)
显然在某些情况下CC无法达到目标，比如N=3,K=1。此时CC会重新买一些新的瓶子(新瓶子容量无限，开始时有1升水)，以到达目标。
现在CC想知道，最少需要买多少新瓶子才能达到目标呢？
输入输出格式
输入格式：
一行两个正整数， N,K(1<=N<=10^9，K<=1000)。
输出格式：
一个非负整数，表示最少需要买多少新瓶子。
输入输出样例
输入样例#1：
样例1：
3 1
样例2：
13 2
样例3：
1000000 5
输出样例#1：
样例1：
1
样例2：
3
样例3：
15808
手推一下各种数据可以发现，最终状态应该是k个瓶子各有2^x的水量，总和大于n。
贪心，使k个瓶子里的水尽量少，而总和大于n。
刚开始的做法是贪心减去不大于剩余水量的最大的2的幂，然后计算需要添加多少水。
80分，懒得改了，直接写标算。
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #define LL long long 8 using namespace std; 9 LL n,k; 10 LL smm=0; 11 LL p[35]; 12 int main(){ 13 int i,j; 14 scanf("%lld%lld",&n,&k); 15 p[1]=1; 16 for(i=2;i<=32;i++){ 17 p[i]=p[i-1]*2; 18 } 19 smm=0; 20 int pos=32; 21 while(p[pos-1]>=n)pos--; 22 LL ans=p[pos]-n; 23 if(ans<0)ans=p[32]; 24 pos--; 25 while(k--){ 26 while(smm+p[pos-1]>=n)pos--; 27 ans=min(ans,abs(smm+p[pos+1]-n)); 28 smm+=p[pos]; 29 if(smm>=n){ 30 printf("%lld\n",min(ans,smm-n)); 31 return 0; 32 } 33 pos--; 34 } 35 printf("%lld\n",ans); 36 return 0; 37 }
标算使用了位运算的思想。
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #define LL long long 8 using namespace std; 9 bool b[33]; 10 int cnt; 11 LL s=0; 12 LL ans=0; 13 LL n,k; 14 int main(){ 15 scanf("%lld%lld",&n,&k); 16 int i,j; 17 for(i=31;i>=0;i--){ 18 LL tmp=pow(2,i); 19 if(n>=tmp){ 20 n-=tmp; 21 b[i]=1; 22 cnt++; 23 } 24 } 25 s=0; 26 while(cnt>k){ 27 for(i=s;;i++){ 28 if(b[i]){ 29 s=i;b[i]=0; 30 break; 31 } 32 } 33 for(i=s+1;;i++){ 34 if(b[i]){ 35 b[i]=0; 36 cnt--; 37 int x=i+1; 38 while(b[x]){ 39 b[x]=0; 40 x++; 41 cnt--; 42 } 43 b[x]=1; 44 ans+=pow(2,i)-pow(2,s); 45 s=x; 46 break; 47 } 48 } 49 } 50 cout<<ans<<endl; 51 return 0; 52 }