题目描述
一天，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 #include3 #include 4 #include 5 #include 6 #include 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 #include3 #include 4 #include 5 #include 6 #include 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< <