- Quiz
- AC
- 解説
- 今日のゴミはまだ出さない
- 昨日のゴミは出さないと行けないので袋を使って捨てる。その時に袋の容量に余りがあれば今日の分のゴミも詰めて捨てることで、翌日を楽にする
- これを貪欲にやる
int main(){ // input ll N,K; cin>>N>>K; VI A(N); rep(i, N) cin >> A[i]; A.push_back(0); A.push_back(0); A.push_back(0); ll cnt=0; FOR(i,1, N+1){ // 昨日の分を捨てる cnt += A[i-1]/K; A[i-1]%=K; if(A[i-1]>0){ cnt++; ll rest_capacity = K-A[i-1]; A[i] -= rest_capacity; if(A[i]<0) A[i]=0; } } p(cnt); return 0; }