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

sataniC++

C++、競プロ、数学などについて色々考えたりします。

yukicoder No.5 数字のブロック

yukicoder yukicoder-★

問題

問題のURLはこちらです。
No.5 数字のブロック - yukicoder


考えたこと

W_iをうまく組み合わせてちょうどLになるように…!」って問題でも無いので、W_iの小さい順にLから引くたびにカウントしていき、Lがマイナスになった時点でループを終了しその時の個数を出力したらいいですね。


コード(C++)

#85612 No.5 数字のブロック - yukicoder

#include <iostream>
#include <algorithm>
#include <vector>

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    int L, N, ans=0;
    std::cin >> L >> N;
    std::vector<int> W(N);
    for(int i=0; i<N; ++i){
        std::cin >> W[i];
    }
    std::sort(W.begin(), W.end(), std::less<int>());
    for(;ans<N; ++ans){
        L -= W[ans];
        if(L<0) break;
    }
    std::cout << ans << "\n";

    return 0;
}

コードの説明など

std::sort(W.begin(), W.end(), std::less<int>());

W_iを小さい順に値を取り出したいため、あらかじめW_iの配列を昇順にソートしておきます。

for(;ans<N; ++ans){
    L -= W[ans];
    if(L<0) break;
}

そして、LからW_iを引き、その時にLが負になっていなければ、個数を格納する変数ansにカウントしていき、Lが負になった時点でループを抜けます。


備考

制限が1\leq N\leq 10000と緩いので、全探索でもしない限りTLEなどにはならないと思います。
計算量はO(N)ですかね?


感想など

考え方など、基本的な問題なのですぐに解法を思いついて一発AC出来るといいですね。
(この記事を書くにあたって改めて問題解いて提出してみたら2WAになってしまったのは内緒)