闪闪发光
原题链接
问题 I: 闪闪发光
时间限制: 1 Sec 内存限制: 128 MB
提交: 675 解决: 182
[提交] [状态] [命题人:外部导入]
题目描述
一所位于云南昆明的中医药本科院校--云南中医学院。
因为报考某专业的人数骤减，正面临着停招的危机。
其中有九名少女想到一条妙计——成为偶像，
只要她们成为偶像，学校的名气便会增加，而报考的人数亦会上升。
就这样，九位个性鲜明的少女决定一起努力成为偶像。
希望可以凭借偶像的名气增加生源来挽救自己所喜爱的专业，让自己的学校闪闪发光。
她们为了成为偶像，第一步对于她们来说是减肥！
这里有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一组。
规律：两个1可以合并为一个2，两个2可以合并为一个3，两个3可以合并为一个4...
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,x,vis[2000010],sum;
int main()
{while(~scanf("%d",&n)){memset(vis,0,sizeof(vis));sum=0;for(int i=0;i<n;i++){scanf("%d",&x);vis[x]++;}for(int i=0;i<=2000005;i++){if(vis[i]){vis[i+1]+=vis[i]/2;vis[i]=vis[i]%2;}if(vis[i])sum++;}printf("%d\n",sum);}return 0;
}
闪闪发光
原题链接
问题 I: 闪闪发光
时间限制: 1 Sec 内存限制: 128 MB
提交: 675 解决: 182
[提交] [状态] [命题人:外部导入]
题目描述
一所位于云南昆明的中医药本科院校--云南中医学院。
因为报考某专业的人数骤减，正面临着停招的危机。
其中有九名少女想到一条妙计——成为偶像，
只要她们成为偶像，学校的名气便会增加，而报考的人数亦会上升。
就这样，九位个性鲜明的少女决定一起努力成为偶像。
希望可以凭借偶像的名气增加生源来挽救自己所喜爱的专业，让自己的学校闪闪发光。
她们为了成为偶像，第一步对于她们来说是减肥！
这里有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一组。
规律：两个1可以合并为一个2，两个2可以合并为一个3，两个3可以合并为一个4...
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,x,vis[2000010],sum;
int main()
{while(~scanf("%d",&n)){memset(vis,0,sizeof(vis));sum=0;for(int i=0;i<n;i++){scanf("%d",&x);vis[x]++;}for(int i=0;i<=2000005;i++){if(vis[i]){vis[i+1]+=vis[i]/2;vis[i]=vis[i]%2;}if(vis[i])sum++;}printf("%d\n",sum);}return 0;
}