CF Croc Champ 2013 - Finals (online version, Div. 1) C(greedy)

欲張りだが、考えを間違えやすい.各ブロックに対して、それより大きいメモリを探して彼を保存します.ただし,与えられたメモリデータを直接処理するのではなく,まず各メモリを2^iに分ける.(ここでは、与えられたデータの特殊性に気づくべきである.2^bi)、そうでなければ貪欲は誤りである.そして、各ブロックがちょうどそれより大きいことを探して、アナログ進数減算で行い、現在のビットがa[i]がb[i]より大きい場合、ansは直接b[i]を加え、そうでなければaは前方にビットを借り、具体的な方法はコードを参照する.十分な数を借りることができれば、ans+=b[i],そうでなければans+=a[i].最後に説明します.この問題はcin coutになります.

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
typedef long long LL;
using namespace std;
const int maxn = 30 + 5;
const int INF = 1000000000;

int a[maxn],b[maxn];

int main(){
    int n,m;
    while(cin >> n >> m){
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        int tem;
        for(int i = 0;i < n;i++){
            scanf("%d",&tem);
            int cnt = 0;
            while(tem){
                if(tem%2 == 1) a[cnt]++;
                tem  = tem / 2;
                cnt++;
            }
        }
        for(int i = 0;i < m;i++){
            scanf("%d",&tem);
            b[tem]++;
        }
        int ans = 0;
        for(int i = 0;i < maxn;i++){
            while(a[i] < b[i]){
                int tag = 0;
                 for(int j = i+1;j < maxn;j++){//  
                    if(a[j]){
                        for(int k = i+1;k < j;k++) a[k]++;
                        a[j]--;
                        a[i] += 2;
                        tag = 1;
                        break;
                    }
                }
                if(tag == 0) break;
            }
            ans += min(a[i],b[i]);
        }
        printf("%d
",ans);
    }
    return 0;
}