Yukicoder005 数字のブロック

問題概要

幅$L$の箱がある。今$N$($N\leqq10^4$)個のブロックを持っており、それぞれのブロックの長さは$w[i]$($1\leqq w[i]\leqq L$)である。 箱にブロックを詰めるときに最大で何個詰めることができるか。

yukicoder005

解法

小さい順に敷き詰めるとするとしたときに、最後の2つについて入らなかったときブロックの幅を$a$,$b$とする。($a$<$b$)

$a+b ≦ c+d$なので$(a≦c,b≦d)$、小さい順に敷き詰めるのが良い。

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VL = vector<LL>;        using VVL = vector<VL>;
    
    #define ALL(a)  begin((a)),end((a))
    #define SORT(c) sort(ALL((c)))
    #define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    
    LL N, L;
    
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> L >> N;
        VL a(N);
        FOR(i, 0, N) {
            cin >> a[i];
        }
    
        SORT(a);
        FOR(i, 0, N) {
            if (L - a[i] >= 0) {
                ans++;
                L -= a[i];
            }
        }
        cout << ans << "\n";
    
        return 0;
    }