2782:Bin Packing

keyword

Greedy　C++

概要

n(<10^5)本の商品の長さとビンの長さlが与えられる。このとき、同じビンに入るのは2つまで商品を入れてもよい。もちろん長さの和はlを越えないようにする。最小でビンは何本必要か求める問題。
しばらく考えて見るけど同じビンに2つまでしか入らないという制約から貪欲方で良さそう。つまり、長いものから詰めていって余裕があるなら残りに詰められる中で最長のものを詰めればよい。2分探索したいのでmultisetで実装(今考えると何故vector or 配列で実装しなかったのか謎)。upper_boundとlower_boundを間違えたけど修正したら無事通った。

int main(){
    int i, n, l, x, ans=0;
    multiset<int> ls;
    ITER(ls) it;
    scanf("%d%d",&n,&l);
    REP(i,n){
        scanf("%d",&x);
        ls.insert(x);
    }

    //EACH(ls,it)cout<<*it<<endl;

    if(1)while(!ls.empty()){
        x = *ls.rbegin();
        it = ls.end();
        it--;
        ls.erase(it);
        it = ls.upper_bound(l-x);
        if(it!=ls.begin()){
            it--;
            ls.erase(it);
        }
        ans++;
    }

    printf("%d\n",ans);

    return 0;
}