巧克力棒(chocolate)
Time Limit:1000ms Memory Limit:64MB
题目描述
LYK 找到了一根巧克力棒，但是这根巧克力棒太长了，LYK 无法一口吞进去。
具体地，这根巧克力棒长为 n，它想将这根巧克力棒折成 n 段长为 1 的巧克力棒，然后
慢慢享用。
它打算每次将一根长为 k 的巧克力棒折成两段长为 a 和 b 的巧克力棒，此时若 a=b，则
LYK 觉得它完成了一件非常困难的事，并会得到 1 点成就感。
LYK 想知道一根长度为 n 的巧克力棒能使它得到最多几点成就感。
输入格式(chocolate.in)
第一行一个数 n。
输出格式(chocolate.out)
一个数表示答案。
输入样例
7
输出样例
4
数据范围
对于 20%的数据 n<=5。
对于 50%的数据 n<=20。
对于 80%的数据 n<=2000。
对于 100%的数据 n<=1000000000。
没想到
贪心做法
#include<iostream> #include<cstdio> #include<queue> #include<vector> #include<cstring> #include<algorithm> using namespace std; long long n,ans; int main() { freopen("chocolate.in","r",stdin); freopen("chocolate.out","w",stdout); cin>>n; ans=n; while(n) { ans-=n%2; n/=2; } cout<<ans; return 0; }
还有一个归纳
我们对c(n)进行归纳。
当c(n)=1时，即n=2^k，ans(n)显然=(n-1)。
我们假设c(n)<=x的情况下ans(n)=n-c(n)都成立。
当c(n)=x+1时，我们要证明ans(n)=n-c(n)。
令j为不超过n的2的幂次的最大值，有ans(n)=ans(n-j)+ans(j)=n-j-(c(n)-1)+j-1=n-c(n)。
即ans(n)的下界为n-c(n)。 将ans(n)分成两个数i,j时有c(i)+c(j)>=c(n)。
当i不等于j时，有ans(n)<=i-c(i)+j-c(j)<=n-c(n)。当i=j时，有c(i)+c(j)=2*c(n)，ans(n)<=i-c(i)+j-c(j)+1<=n-c(n)*2+1，c(n)是正整数。
综上，ans(n)的上界也为n-c(n)。假设成立。