1984: 閃閃發(fā)光

Time Limit:?1 Sec??Memory Limit:?128 MB
Submit:?75??Solved:?23
[Submit][Status][Web Board]

Description

一所位于云南昆明的中醫(yī)藥本科院校--云南中醫(yī)學(xué)院。

因為報考某專業(yè)的人數(shù)驟減，正面臨著停招的危機。

其中有九名少女想到一條妙計——成為偶像，

只要她們成為偶像，學(xué)校的名氣便會增加，而報考的人數(shù)亦會上升。

就這樣，九位個性鮮明的少女決定一起努力成為偶像。

希望可以憑借偶像的名氣增加生源來挽救自己所喜愛的專業(yè)，讓自己的學(xué)校閃閃發(fā)光。

她們?yōu)榱顺蔀榕枷?#xff0c;第一步對于她們來說是減肥！

這里有n個重物，第i個重物的重量是2^{w_i}。她們每天任務(wù)要完成的重量是n個重物的重量和。

每次舉重的重量和必須是2的冪，重物數(shù)量不要求。

但是為了方便，要使舉重的次數(shù)最少。

Input

多組數(shù)據(jù)。
每組數(shù)據(jù)第一行一個整數(shù)n。(1 <= n <= 10^6)
第二行有n個整數(shù)w_1,w_2,...,w_n。(0 <= w_i <= 1000000)

Output

輸出最少的舉重次數(shù)。

Sample Input

51 1 2 3 3

Sample Output

2

HINT

1,1,2一組;

3,3一組。

解析：要求最少，那么盡可能的對重量相稱的合并成一組，注意：重量是2的冪，這樣set就很好用了，詳解看代碼。

代碼：

#include<cstdio> #include<algorithm> #include<set> using namespace std;set<int> s; int main() {int n,x;while(~scanf("%d",&n)){s.clear();while(n--){scanf("%d",&x);while(s.find(x)!=s.end())//循環(huán)找{s.erase(x);x++;//合并比如1 1合并一起就為2.題目要求的重量為2 的冪，所以可以這樣合并。}s.insert(x);}printf("%d\n",s.size());}return 0; }

總結(jié)

以上是生活随笔為你收集整理的zcmu-1984的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。