ZOJ 3498(Javabeans)

题目分析：把每个盒子看成集合。有n个集合，分别有1…n个元素。具体每种集合有多少个是没意义的，因为我们可以把具有相同元素的集合同时操作，所以我们可以用集合的种类代替集合的个数。假设，每次选取k个集合。从这k个集合里拿东西，则这k个集合拿过之后还是k个不同的集合（有可能有一个成空集），所以至少还有(k-1)个不同的集合，而除这k个外还有(n-k)个不同的集合。所以拿完之后不同集合的个数至少变为了r=max(k-1,n-k)。考虑当n是偶数时当k=n/2时，r取最小值，max(k-1,n-k)=n/2，当n为奇数时，k=(n+1)/2时,r取最小值max(k-1,n-k)=(n-1)/2。这个最小值是剩余集合数的一个下界。

其实这个下界是可以达到的：

n是偶数时，从元素个数不少于n/2的全部集合里都拿n/2个，则，剩余集合元素个数变为了1,2……n/2，问题规模缩小了一半。

n是奇数时，从元素个数不少于(n+1)/2的集合里都拿(n+1)/2个，则剩余集合元素个数变为了1,2,…(n-1)/2，问题规模也缩小了一半。

而在c语言中，除以2是下取整的，所以无论n为奇数还是偶数，一次操作之后集合个数至少变成了n/2,并且有办法可以达到这个最小值。

于是，最少拿的次数就是每次把n不断除以2，除到0为止。即n的2进制表示

代码：

#include<iostream>
#include<cstdio>
typedef long long ll;
int main(){
	ll n,ans,times;
	scanf("%lld",×);
	while(times--){
		scanf("%lld",&n);
		ans=0;
		while(n){
			ans++;
			n/=2;
		}
		printf("%lld\n",ans);
	}
	return 0;
}