问题 G: Fancy 的硬币

硬币"/>

问题 G: Fancy 的硬币

问题 G: Fancy 的硬币

Fancy 出去培训的时候得到了好多一块钱（买东西居然全都找硬币），Fancy 想尽快把它们用出去。但是一个一个查硬币实在太麻烦了，所以机智的 Fancy 想了一个方法：先把硬币数好分开装在一些小袋子里，这样掏钱的时候拿出几个袋子就解决了（忽略收银员眼上的黑线）。

n表示 Fancy 拥有硬币的个数，求 Fancy 至少要用多少个袋子装这些硬币，才能使自己对于任意 ≤n的钱数都能用某些袋子的钱数之和表示出来（一个袋子只能用一次）。

分析：假设袋子数量为i，则i个袋子最终会有2^i-1种组合。（减一是因为没有零这一种情况）。所以剩下的很明确了。

#include<bits/stdc++.h>
/*#include <stdio.h>
#include <algorithm>
#include<iostream>
#include <stdlib.h>*/
//#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
typedef long long ll;
const int maxn=1e6+50;
const int N=1e6+5;
const ll mod =1e9+7;
const int inf=2e9+7;
int a[25];
int main()
{ll n;scanf("%lld",&n);ll i=0;while(n>=pow(2,i)){if(n<pow(2,i+1)){printf("%lld\n",i+1);return 0;}i++;}
}

不解的是，我第一次用的是位运算超时了，pow函数却过了。

超时代码

#include<bits/stdc++.h>
/*#include <stdio.h>
#include <algorithm>
#include<iostream>
#include <stdlib.h>*/
//#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
typedef long long ll;
const int maxn=1e6+50;
const int N=1e6+5;
const ll mod =1e9+7;
const int inf=2e9+7;
int a[25];
int main()
{ll n;scanf("%lld",&n);ll i=0;while(n>=(1ll<<i)){if(n<(1ll<<(i+1))){printf("%d\n",i+1);return 0;}i++;}
}