首页 > 代码库 > 1596 搬货物

1596 搬货物

现在有n个货物,第i个货物的重量是 2wi 。每次搬的时候要求货物重量的总和是一个2的幂。问最少要搬几次能把所有的货物搬完。

样例解释:

1,1,2作为一组。

3,3作为一组。

Input
单组测试数据。第一行有一个整数n (1≤n≤10^6),表示有几个货物。第二行有n个整数 w1,w2,...,wn,(0≤wi≤10^6)。
Output
输出最少的运货次数。
Input示例
样例输入151 1 2 3 3
Output示例
样例输出12

 

进行二进制进位运算,当有一位为1时sum++,直至最后。

 

AC代码:

 1 #include<bits/stdc++.h> 2 #define maxn 1000100 3 int w[maxn];  4 int main() 5 { 6     int n,i; 7     while(scanf("%d",&n)!=EOF) 8     { 9         memset(w,0,sizeof(w)); 10         while(n--)11         {12             scanf("%d",&i);13             w[i]++; 14         } 15         int sum=0;16         for(int j=0;j<maxn;++j)17         {18             if(w[j]>1)19             {20                 w[j+1]+=w[j]/2;21                 w[j]%=2; 22             } 23             if(w[j]==1)24                 ++sum; 25         } 26         printf("%d\n",sum); 27     } 28     return 0;29 } 

 

1596 搬货物