AtCoder Beginner Contest 116:C - Grand Garden
https://atcoder.jp/contests/abc116/tasks/abc116_c
実装に時間がかかってしまいました。
方針
花の高さが最初 で、これに水をかけることで高さを 0 にすると考えました。
水やりは連続した花にしか同時には行えないので、高さが 0 になった区間をまたぐ水やりはできません。そこで「高さが 1 以上の区間を出来るだけ広くとって、そこに水やりをする」という操作を繰り返します。
ソースコード
#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 ans = 0; while(true){ // 区間の左端を求める。 // h[i] != 0 になる最初の i が左端。 int s = -1; for(int i=0; i<N; i++){ if(h[i] != 0){ s = i; break; } } // s = -1 のとき、全ての花の高さが 0 。 if(s==-1) break; // 区間の右端を求める。 // i = s から始めて、h[i] = 0 となる i の左隣が右端。 // ただし h[N-1] が右端の場合もあるので注意する。 int g = -1; for(int i=s; i<N; i++){ if(h[i]==0){ g = i-1; break; } if(i==N-1) g = N-1; } // 区間の中で最も低い花の分だけ、高さを低く出来る。 int hmin = 101; for(int i=s; i<=g; i++){ hmin = min(hmin, h[i]); } for(int i=s; i<=g; i++){ h[i]-=hmin; } ans += hmin; } cout << ans << endl; }