ABC116 C Grand Garden 解説
問題文
・花がN本植えられている。
・連続している好きな区間を選んで、その区間内の花の高さを+1する。
・N個の数列が与えられていて、それらは各花の目標の高さを表している。
・すべての花を目標の高さにしたい。最短何回水やりをすればいいか求める。
ACコード
解説
・この手の問題は、やることと真逆のことを考えるとうまくいくことがある。
・つまり、もともと目標の高さに生えている花に、好きな区間の花の高さを-1する枯葉剤をまくことを考える。
・最短回数を求めるので、できるだけ多くの花に枯葉剤をまいたほうがいい。しかし、すでに高さが0になっている花に枯葉剤をまいてはいけない。
⇒実際には高さを上げているので、目標の高さを超えてしまうから
・なので、基準の花(最初は左端の花)から高さを調べていって、高さが0の花が初めて出てくるまでの範囲内に枯葉剤をまいて、0が出てきたら再び基準まで戻りまた同じように枯葉剤をまく。そして、基準の花も0になったならば、その時点で一番左にある高さ1以上の花を基準にして高さを調べていくと最短で花を枯らす(実際には水をやって高さを上げる)ことができる。
解いた感想
体感難易度:☆4
・JOI予選で同じような問題に遭遇したので考察自体は楽だった。
・for文とbreak文を使うことでスマートに0になるタイミングを調べられる(0が出てきたらそこでbreak)。これはほかの問題にも応用できそうな気がした。
