読者です 読者をやめる 読者になる 読者になる

Facebook Hacker Cup 2017 Qualification Round - Lazy Loading

問題

Lazy Loading | Facebook Hacker Cup 2017 Qualification Round

考察

一番上の重さだけが関係あり、他は個数しか見られません。
そのため、「一番上に手持ちの一番重たいもの」を使い、残りは個数だけ見て、「軽いものから順番に」使って50ポンドを超えたら止めればよいです。

このような処理は事前にソートしておいて、dequeに詰めると楽ちんです。

コード

int solve() {
    int N;
    cin >> N;

    vi W(N);
    rep(i, N)
        cin >> W[i];

    sort(all(W), greater<int>());
    deque<int> deq;
    rep(i, N)
        deq.push_back(W[i]);

    int ans = 0;
    while(!deq.empty()) {
        int f = deq.front();
        deq.pop_front();

        int rem = (int)ceil(50.0 / f);
        if(deq.size() < rem - 1)
            break;

        ans++;

        rep(i, rem-1) {
            deq.pop_back();
        }
    }

    return ans;
}

int main() {
    int T;
    cin >> T;
    rep(__t, T) {
        cout << "Case #" << __t + 1 << ": ";
        cout << solve() << endl;
    }

    return 0;
}

感想

Aより簡単に見えるので何とも不安になる問題でした。