问题 I: 闪闪发光

[提交] [状态] [命题人:外部导入]

题目描述

一所位于云南昆明的中医药本科院校--云南中医学院。

因为报考某专业的人数骤减，正面临着停招的危机。

其中有九名少女想到一条妙计——成为偶像，

只要她们成为偶像，学校的名气便会增加，而报考的人数亦会上升。

就这样，九位个性鲜明的少女决定一起努力成为偶像。

希望可以凭借偶像的名气增加生源来挽救自己所喜爱的专业，让自己的学校闪闪发光。

她们为了成为偶像，第一步对于她们来说是减肥！

这里有n个重物，第i个重物的重量是2^{w_i}。她们每天任务要完成的重量是n个重物的重量和。

每次举重的重量和必须是2的幂，重物数量不要求。

但是为了方便，要使举重的次数最少。

输入

多组数据。
每组数据第一行一个整数n。(1 <= n <= 10^6)
第二行有n个整数w_1,w_2,...,w_n。(0 <= w_i <= 1000000)

输出

输出最少的举重次数。

样例输入

复制样例数据

5

1 1 2 3 3

样例输出

2

提示

1,1,2一组;
3,3一组。

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+100;

int s[maxn]= {0};

int main()

{

    //freopen("in.txt", "r", stdin);

    int n;

    while(scanf("%d",&n)!=-1)

    {

        memset(s,0,sizeof(s));

        for(int i=0,t; i<n; i++)

        {

            scanf("%d",&t);

            s[t]++;

        }

        for(int i=0; i<maxn; i++)

        {

            if(s[i]>1)

            {

                int t=s[i]/2;

                s[i]%=2;

                s[i+1]+=t;//它的下一次幂加t

            }

        }

        int g=0;

        for(int i=0; i<maxn; i++)

            if(s[i])

                g++;

        printf("%d\n",g);

    }

    return 0;

}