yukicoder No.5 数字のブロック
考えたこと
「をうまく組み合わせてちょうどになるように…!」って問題でも無いので、の小さい順にから引くたびにカウントしていき、がマイナスになった時点でループを終了しその時の個数を出力したらいいですね。
コード(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>());
を小さい順に値を取り出したいため、あらかじめの配列を昇順にソートしておきます。
for(;ans<N; ++ans){ L -= W[ans]; if(L<0) break; }
そして、からを引き、その時にが負になっていなければ、個数を格納する変数ansにカウントしていき、が負になった時点でループを抜けます。
備考
制限がと緩いので、全探索でもしない限りTLEなどにはならないと思います。
計算量はですかね?
感想など
考え方など、基本的な問題なのですぐに解法を思いついて一発AC出来るといいですね。
(この記事を書くにあたって改めて問題解いて提出してみたら2WAになってしまったのは内緒)