51Nod 1596 搬貨物 （數學

1596 搬貨物

題目來源： CodeForces

基準時間限制：1 秒 空間限制：131072 KB 分值: 10 難度：2級算法題 收藏 關注

現在有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示例

樣例輸入1

5

1 1 2 3 3

Output示例

樣例輸出1

2

很有意思的一道題 （利用二進制2333

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
const int mod = +;
#define N 2000010
int arr[N]; 
int main()
{
    int n;
    while(~scanf("%d",&n)) {
        int k;
        memset(arr,,sizeof(arr));
        for(int i = ;i < n; i++) {
            scanf("%d",&k);
            arr[k]++;
        }
        int sum = ;
        for(int i = ;i < N; i++) {
            if(arr[i] > ) {
                arr[i+] += arr[i]/;
                arr[i] %= ;
            }
            if(arr[i] == ) sum++;
        }
        printf("%d\n",sum);
    }
return ;
}