SRM 598 div1 easy: BinPacking

サンプルがすごく丁寧。

問題

TopCoder Statistics - Problem Statement

解法

ビンの大きさが 300 で固定であり, かつ入れる品物の大きさが 100 〜 300 で固定されているので,

• 200 より大きい品物は一つで入れるしかない
• 101 以上 200 以下の品物は それより小さい品物と組み合わせられるなら, なるべく大きい品物と組み合わせながらビンにつめる
• 残った大きさ 100 の品物は, 3 個ずつビンに入れていく

とやるのが最適です。

bool done[55];

class BinPacking {
public:
    int minBins(vector <int> item) {
        sort(item.begin(), item.end());
        int n = item.size();
        int last = n-1;
        int ans = 0;
        while (last >= 0 && item[last] > 200) {
            last--;
            ans++;
        }
        memset(done, false, sizeof(done));
        for (int i = last; i >= 0 && item[i] > 100; i--) {
            if (done[i]) continue;
            int index = i-1;
            for (; index >= 0; index--) if (!done[index] && item[i]+item[index] <= 300) break;
            ans++;
            done[i] = true;
            if (index >= 0) {
                done[index] = true;
            }
        }
        int cnt = 0;
        for (int i = 0; i < n; i++) if (!done[i] && item[i] == 100) cnt++;
        ans += (cnt+2)/3;
        return ans;
    }
};