51nod-1596-搬貨物

現在有n個貨物，第i個貨物的重量是 2 w i 2^{wi} 2wi 。每次搬的時候要求貨物重量的總和是一個2的幂。問最少要搬幾次能把所有的貨物搬完。

樣例解釋：

1，1，2作為一組。

3，3作為一組。

Input

單組測試資料。

第一行有一個整數n (1≤n≤10^6)，表示有幾個貨物。

第二行有n個整數 w1,w2,…,wn，(0≤wi≤10^6)。

Output

輸出最少的運貨次數。

Sample Input

樣例輸入1

5

1 1 2 3 3

Sample Output

樣例輸出1

2

我們知道， 2 x + 2 x = 2 x + 1 2^x+2^x=2^{x+1} 2x+2x=2x+1.

于是，這道題就成功轉化成了大暴力（？）。

（話題上标的是二進制…

讀入時記錄每一位的個數。

枚舉每一位，進位，答案加上這一位的數字。

然後，我做出來的竟然要用讀入優化（否則T掉）。不知道有沒有什麼優化之類的。

存在進位，是以不能隻枚舉到最大值，需要再多枚舉幾位。

詳見代碼。

#include<cstdio>
#include<algorithm>
#define maxn 1000100
using namespace std;
int n,cnt[maxn+5],ans,m;
int getint()
{
	int res=0;
	char c=0;
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9')
	{
		res=res*10+c-'0';
		c=getchar();
	}
	return res;
}
int main()
{
	n=getint();
	for(int i=1;i<=n;i++)
	{
		int x=getint();
		cnt[x]++;
		m=max(m,x);
	}
	for(int i=0;i<=m+100;i++)
	{
		if(cnt[i]>1)
		{
			cnt[i+1]+=cnt[i]>>1;
			cnt[i]&=1;
		}
		ans+=cnt[i];
	}
	printf("%d\n",ans);
}