首页 > 代码库 > 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 3Output示例样例输出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 搬货物
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。