公式

A - 連鎖するバケツ / Chaining Buckets 解説 by physics0523


初心者の方へ


番号の小さいバケツから順に水が満たされるので、以下の通りにシミュレーションを行えばよいです。

  • 最初、流れてくる水の残量は \(W\) である。
  • \(i=1,2,\dots,N\) の順に以下を繰り返す。
    • もし \(W\)\(C_i\) 未満であれば、バケツ \(i\) は満たされず、答えは \(i-1\) である。
    • もし \(W\)\(C_i\) 以上であれば、バケツ \(i\) は満たされる。 \(W\) から \(C_i\) を引く。
  • ここまでで答えが確定しなければ全てのバケツが水で満たされ、答えが \(N\) となることが分かる。

一連のシミュレーションは for 文と if 文の組み合わせ等で実装できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll N,W;
  cin >> N >> W;
  vector<ll> C(N);
  for(auto &nx : C){cin >> nx;}
  for(ll i=0;i<N;i++){
    W-=C[i];
    if(W<0){
      cout << i << "\n";
      return 0;
    }
  }
  cout << N << "\n";
  return 0;
}

投稿日時:
最終更新: