yukicoder No.5 数字のブロック 解説

問題文

解説

できるだけ軽いものから載せていく
直感的にもそうだろうが、軽いものからだんだん重たいものへと載せていく方がいっぱい乗せられる。
事前に昇順sortしておけばあとは左から順番に乗せられるか確かめていくだけ。
sortがボトルネックで$O(NlogN)$なので十分間に合う。

C++23の解答例

#include <bits/stdc++.h>
using namespace std;

int main(){
  int l,n;cin>>l>>n;
  vector<int> w(n);
  for(int i=0;i<n;i++)cin>>w[i];
  sort(w.begin(),w.end());
  for(int i=0;i<n;i++){
    l-=w[i];
    if(l<0){
      cout<<i<<endl;
      return 0;
    }
  }
  cout<<n<<endl;
}