现在的位置: 首页 > 综合 > 正文

Codeforces CROC problem C

2013年09月09日 ⁄ 综合 ⁄ 共 630字 ⁄ 字号 评论关闭

 

题意:给你一些 RMA 空间,要你使用这些 RAM 空间储存数组,求可以存储的数组个数的最大。。。

 

/*
贪心。。 
进一步理解二进制算法 。。。 
*/ 
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
#define manx 1000009
int a[32],b[manx];

int main(){
    int n,m;
    while(cin>>n>>m){
        for(int i=0;i<32;i++) a[i]=0;
        for(int i=0;i<n;i++){
            int x;
            scanf("%d",&x);
            for (int k=0; k<32; ++k) a[k] += x>>k&1;  //查看二进位是否存在 
        }    
        for(int i=0;i<m;i++)
            scanf("%d",&b[i]); 
        sort(b,b+m);
        int sum=0,i,j,k;
        for( i=0;i<m;i++){
            for(j=b[i]; j<32 && !a[j]; ++j);//找到第一个 a[j] 不为 0 的值 
            if(j==32) break;
            ++sum; --a[j];
            for(k=b[i]; k<j; ++k) ++a[k];//如果a[j]>b[k],处理剩下的a[j]-b[k]的空间 
                                         //由于二进制的特殊性,a[j]-b[i] 可以转化为二进制的储存
        }
        cout<<sum<<endl;
    }
}
/*

5 3
8 4 3 2 2
3 2 2

10 6
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0

*/

 

抱歉!评论已关闭.