Official
A - 連鎖するバケツ / Chaining Buckets Editorial
by
A - 連鎖するバケツ / Chaining Buckets Editorial
by
physics0523
初心者の方へ
- AtCoder をはじめたばかりで何をしたらよいか分からない方は、まずは practice contest の問題A「Welcome to AtCoder」を解いてみてください。基本的な入出力の方法が載っています。
- また、プログラミングコンテストの問題に慣れていない方は、AtCoder Beginners Selection の問題をいくつか解いてみることをおすすめします。
- C++入門 AtCoder Programming Guide for beginners (APG4b) は、競技プログラミングのための C++ 入門用コンテンツです。
- Python入門 AtCoder Programming Guide for beginners (APG4bPython) は、競技プログラミングのための Python 入門用コンテンツです。
番号の小さいバケツから順に水が満たされるので、以下の通りにシミュレーションを行えばよいです。
- 最初、流れてくる水の残量は \(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;
}
posted:
last update:
