现在有 n 个货物, 第 i 个货物的重量是
2
wi
. 每次搬的时候要求货物重量的总和是一个 2 的幂. 问最少要搬几次能把所有的货物搬完.
样例解释:
1,1,2 作为一组.
3,3 作为一组.
Input
单组测试数据.
第一行有一个整数 n (1n10^6), 表示有几个货物.
第二行有 n 个整数 w1,w2,...,wn,(0wi10^6).
Output
输出最少的运货次数.
两个质量相同的可以一起搬, 注意, 这里用 scanf 需要读入挂, 不然会 T
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <cstdio>
- #include <vector>
- #include <queue>
- #include <stack>
- #include <cstdlib>
- #include <iomanip>
- #include <cmath>
- #include <cassert>
- #include <ctime>
- #include <map>
- #include <set>
- using namespace std;
- #pragma comment(linker, "/stck:1024000000,1024000000")
- #define lowbit(x) (x&(-x))
- #define max(x,y) (x>=y?x:y)
- #define min(x,y) (x<=y?x:y)
- #define MAX 100000000000000000
- #define MOD 1000000007
- #define pi acos(-1.0)
- #define ei exp(1)
- #define PI 3.1415926535897932384626433832
- #define ios() ios::sync_with_stdio(true)
- #define INF 0x3f3f3f3f
- #define mem(a) ((a,0,sizeof(a)))
- typedef long long ll;
- int n,a[1000106],x;
- int read()
- {
- int x=0;
- char ch=getchar();
- while(ch<'0' || ch>'9')ch=getchar();
- while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
- return x;
- }
- int main()
- {
- scanf("%d",&n);
- memset(a,0,sizeof(a));
- for(int i=0;i<n;i++)
- {
- x=read();
- a[x]++;
- }
- int ans=0;
- for(int i=0;i<=1000100;i++)
- {
- ans+=(a[i]%2);
- a[i+1]+=a[i]/2;
- }
- printf("%d\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2582458.html