紙老虎題，有n個盒子，第i個盒子里有i個東西，每次選取一些盒子，然后從這些盒子中每個都取出相同數(shù)目的東西。問至少幾次可以把盒子清空？

         把每個盒子看成集合。有n個集合，分別有1…n個元素。具體每種集合有多少個是沒意義的，因為我們可以把具有相同元素的集合同時操作，所以我們可以用集合的種類代替集合的個數(shù)。假設(shè)，每次選取k個集合。從這k個集合里拿東西，則這k個集合拿過之后還是k個不同的集合（有可能有一個成空集），所以至少還有(k-1)個不同的集合，而除這k個外還有(n-k)個不同的集合。所以拿完之后不同集合的個數(shù)至少變?yōu)榱?/span>r=max(k-1,n-k)。考慮當(dāng)n是偶數(shù)時當(dāng)k=n/2時，r取最小值，max(k-1,n-k)=n/2，當(dāng)n為奇數(shù)時，k=(n+1)/2時,r取最小值max(k-1,n-k)=(n-1)/2。這個最小值是剩余集合數(shù)的一個下界。

其實這個下界是可以達到的：

n是偶數(shù)時，從元素個數(shù)不少于n/2的全部集合里都拿n/2個，則，剩余集合元素個數(shù)變?yōu)榱?/span>1,2……n/2，問題規(guī)模縮小了一半。

n是奇數(shù)時，從元素個數(shù)不少于(n+1)/2的集合里都拿(n+1)/2個，則剩余集合元素個數(shù)變?yōu)榱?/span>1,2,…(n-1)/2，問題規(guī)模也縮小了一半。

而在c語言中，除以2是下取整的，所以無論n為奇數(shù)還是偶數(shù)，一次操作之后集合個數(shù)至少變成了n/2,并且有辦法可以達到這個最小值。

于是，最少拿的次數(shù)就是每次把n不斷除以2，除到0為止。即n的2進制表示中的bit數(shù)。

#include <stdio.h>
typedef unsigned int uint;
uint a[33];
int main()
{
    int t;
    uint i,n;
    a[0]=1;a[1]=2;
    for (i=2;i<33;i++)
        a[i]=2*a[i-1];
    scanf("%d",&t);
    while (t--)
    {
        scanf("%u",&n);
        for (i=1;i<33;i++)
            if (n>=a[i-1]&&n<a[i])
            {printf("%u\n",i);break;}
    }
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a,const void *b)
{
    return (*(double *)a)>(*(double *)b)?1:0;
}
double a[1000];
int main()
{
    int t,i,n;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d",&n);
        for (i=1;i<=n;i++)
            scanf("%lf",&a[i]);
        qsort(a+1,n,sizeof(a[0]),cmp);
        if (n%2) printf("%.3lf\n",a[n/2+1]);
        else printf("%.3lf\n",(a[n/2]+a[n/2+1])/2.0);
    }
    return 0;
}