51Nod-1596 搬货物

博主链接

题目链接

题意：

给你一个n，有n个货物，然后n个整数w1…wn表示第i个货物重2^wi。每次搬运2的幂，求几次可以搬完。

题解：

题目题意其实就是变相的问所有数可以最少组成多少个2的幂数，每两个2^i
可以组成2^(i+1),所以开一个1e6+100 <mark>(多开一百防止类似于1e6个数全是1e6的情况)</mark> 的数组记录下每种重量的数量，然后从小到大扫一遍数组,依次将个数/2加给后一位

代码：

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+500;
int num[maxn];
int main(){
    int n,a;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a);
        num[a]++;
    }
    for(int i=0;i<maxn-1;i++){
        num[i+1]+=num[i]/2;
        num[i]%=2;
    }
    int ans=0;
    for(int i=0;i<maxn;i++)if(num[i])ans++;
    printf("%d\n",ans);
    return 0;
}