首页 > 代码库 > 51Nod - 1596 搬货物
51Nod - 1596 搬货物
51Nod - 1596 搬货物
现在有n个货物，第i个货物的重量是 2wi 。每次搬的时候要求货物重量的总和是一个2的幂。问最少要搬几次能把所有的货物搬完。
样例解释：
1，1，2作为一组。
3，3作为一组。
Input
单组测试数据。 第一行有一个整数n (1≤n≤10^6)，表示有几个货物。 第二行有n个整数 w1,w2,...,wn，(0≤wi≤10^6)。
Output
输出最少的运货次数。
Input示例
样例输入1 5 1 1 2 3 3
Output示例
样例输出1 2
题解：
类似二进制的思路。
极端数据还真的很烦。 （MAXN 需要超过 1e6 + 115, 设 1e6+5 是不行的）
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAXN = 1000000 + 115;
int n, num[MAXN];
int main(){
int a, ans, max_val;
while(scanf("%d", &n) != EOF){
memset(num, 0, sizeof(num));
max_val = 0;
for(int i=0; i<n; ++i){
scanf("%d", &a);
num[a] = num[a] + 1;
if(max_val < a){
max_val = a;
}
}
ans = 0;
for(int i=0; i<=max_val+100 && i<MAXN; ++i){
if(num[i] > 1){
num[i+1] = num[i+1] + (num[i]/2);
num[i] = num[i] % 2;
}
if(num[i] == 1){
ans++;
}
}
printf("%d\n", ans);
}
return 0;
}
或者是：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAXN = 1000000 + 115;
int n, num[MAXN];
int main(){
int a, ans;
while(scanf("%d", &n) != EOF){
memset(num, 0, sizeof(num));
for(int i=0; i<n; ++i){
scanf("%d", &a);
num[a] += 1;
while(num[a] >= 2){
num[a] -= 2;
a = a + 1;
num[a] += 1;
}
}
ans = 0;
for(int i=0; i<MAXN; ++i){
if(num[i]){
ans++;
}
}
printf("%d\n", ans );
}
return 0;
}
51Nod - 1596 搬货物
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。