51nod 1596 搬货物(Codeforces 587A Duff and Weight Lifting)(思维)

题目链接(Codeforces)：http://codeforces.com/contest/587/problem/A

题目链接(51nod)：https://www.51nod.com/Challenge/Problem.html#!#problemId=1596

       题意是输入n，表示有n个哑铃片，然后输入n个数，然后寻找2^a1+2^a2+...+2^ai=2^x(x为任意整数)，如果前i个数满足这个式子，就可以去掉这i片哑铃，问他最少需要几次才能把哑铃片全部去掉。比如第一个样例，1 1 2 3 3，换成2的次方就是2 2 4 8 8，然后我们第一次把前四个去掉，就是2+2+4+8=16，刚好是2的4次方，然后再去掉一个2的3次方，所以最少需要两次。

       思路就是我们换个思路可以发现2^1+2^1=2^2，2^2+2^2=2^3，所以我们可以两个两个合并，看最后剩下多少个不能合并。第一个样例就是1+1=2变成了2 2 3 3，然后2+2=3变成了3 3 3，然后3+3=4变成了4 3，最后就剩下了这个两个数没法合并了。呆码直接按这个思路去模拟就好了。

AC代码：

#include <bits/stdc++.h>
#define maxn 1000010
using namespace std;
int n,pre[maxn << 1],xx;

int main()
{
	scanf("%d",&n);
	memset(pre,0,sizeof(pre));
	for(int i=0;i<n;i++){
		scanf("%d",&xx);
		pre[xx] ++;
	}
	int ans = 0;
	for(int i=0;i<1000050;i++){
		pre[i+1] += (pre[i] / 2);
		ans += (pre[i] % 2);
	}
	printf("%d\n",ans);
	return 0;
}