ABC116 C Grand Garden

問題概要

要素数Nの配列{h[0],h[1],....,h[N-1]}が与えられる。これを、1が連続して現れる配列の和として表すとき、必要な配列の個数の最小値はいくつか？

考えたこと

例えば、h={3,1,2,3,1,1,2}とすると、

=(1,1,1,1,1,1,1)
+(0,0,1,1,0,0,0)
+(0,0,0,1,0,0,0)
+(1,0,0,0,0,0,0)
+(1,0,0,0,0,0,0)
+(0,0,0,0,0,0,1)

という風に、配列hは6つの連続する配列の和として書ける。以下、1が連続する配列を1配列と呼ぶことにする。
コード実装のアイデアとしては、まず配列hを先頭から順に見て行って、h[i] != 0なら、1配列に対応する区間をスタートし、h[i]=0になるか hの最後まで見終わったら区間を終了する。なお、区間中の0でない要素をそれぞれ1減らしていく。
この操作をhの全ての要素が0になるまで繰り返した時の、区間の数の合計が答えとなる。

ソースコード

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

int main() {
  int N;
  cin >> N;
  vector<int> h(N);
  for(int i = 0;i<N;i++){
    cin >> h[i];
  }
  int res = 0;
  while(*max_element(h.begin(),h.end()) >0){//hの全要素が0になるまでやる
    for(int i = 0;i<N;i++){
      if(h[i] != 0){//高さが0でなかったら区間スタート
        res++;
        while(i<N){
          if(h[i] != 0){
            h[i]--;//高さが0でない要素から1を引いていく
            i++;
          }
          if(h[i] == 0) break;//0なら区間終了
        }
      }
    }
  }
  cout << res << endl;
}