闪闪发光

题目描述

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

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

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

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

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

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

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

这里有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一组。

题解

把小的数可以组合的组合起来，不能继续组合的数量就是答案

用优先队列就很简单了；

弹出队首x，如果和接下来的队首相等 就继续弹出队首，将x+1入队

如果不相等 或者队列已经空了 那就计数++;

代码

#include
    
     using namespace std;typedef long long ll;typedef pair
     
       P;#define all(x) x.begin(),x.end()#define readc(x) scanf("%c",&x)#define read(x) scanf("%d",&x)#define read2(x,y) scanf("%d%d",&x,&y)#define read3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define print(x) printf("%d\n",x)#define mst(a,b) memset(a,b,sizeof(a))#define lowbit(x) x&-x#define lson(x) x<<1#define rson(x) x<<1|1#define pb push_back#define mp make_pair#define PI acos(-1.0)const int maxn = 1e6+5;int n;int w[maxn];int ans;int main(){  priority_queue
      
       
        ,greater
        
         > q;  while(read(n)!=EOF){    while(!q.empty()) q.pop();    for(int i = 0 ; i < n; i++){      read(w[i]);      q.push(w[i]);    }    ans = 0;    while(!q.empty()){      int p = q.top();      q.pop();      if(p != q.top() || q.empty()){        ans ++;      //  cout << p <
        
       
      
     
    

队友用数组过的，思想是一样的，需要注意的地方是数组需要开的够大

#include
    
     using namespace std;#define memset(x,y) memset(x,y,sizeof(x))#define memcpy(x,y) memcpy(x,y,sizeof(y))#define pri(x) printf("%d\n",x)#define pri2(x,y) printf("%d %d\n",x,y)#define pris(x) printf("%s\n",x)#define prl(x) printf("%lld\n",x)#define all(x) x.begin(),x.end()#define readc(x) scanf("%c",&x)#define read(x) scanf("%d",&x)#define read2(x,y) scanf("%d%d",&x,&y)#define read3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define print(x) printf("%d\n",x)#define lowbit(x) x&-x#define lson(x) x<<1#define rson(x) x<<1|1#define pb push_back#define mp make_pair#define INF 0x3f3f3f3ftypedef pair
     
       P;typedef long long LL;typedef long long ll;const double eps=1e-8;const int MAXN=1e6+7;const int maxn=5000000+10;const int maxm = 1;const int mod=1e9+7;int n;int T;int ans = 0;int w[maxn];int x;int main(){    while(read(n)!=EOF)    {      int cnt = 0;      memset(w,0);      for(int i = 0 ; i < n; i++){         read(x);         w[x] ++;      }      for(int i = 0; i < 5000000+5; i++)      {         if(w[i] % 2 == 1) cnt++;         w[i+1] += w[i] / 2;      }      printf("%d\n",cnt);    }    return 0;}