0.はじめに

1.問題文

花壇に N 本の花が咲いており、それぞれ 1 , 2 , . . . . . . , N と番号が振られています。最初、全ての花の高さは 0 です。数列 h= { h 1 , h 2 , h 3 , . . . . . . } が入力として与えられます。以下の「水やり」操作を繰り返すことで、すべての k ( 1 ≦ k ≦ N ) に対して花 k の高さを h k にしたいです。

整数 l , r を指定する。 l ≦ x ≦ r を満たすすべての x に対して、花 x の高さを 1 高くする。条件を満たすための最小の「水やり」操作の回数を求めてください。

2.入力例

入力

5
3 1 2 3 1

出力

3.初見の感想

まずどういう水やり方法が正解なのか考えてみる

入力例の場合で考えると下の図の赤線のように水やりすればよいことに気付きます

f:id:nemurin_blog:20190306225309p:plain

赤線の本数をどう数える？

上の図の赤線の本数が水やりの回数、すなわち答えなわけです。

一般的に、線というものには始点と終点の情報しかありません。

今回僕はこの線の始点に着目しました。

線の始点が存在するのはどんな時？

線の始点が存在する場所をより分析してみると、「一つ左の花に比べて、その花の高さが大きい時」に線の始点が存在しています。

つまり、「左の花に比べていくつ花の高さが大きいか」を調べればよかったのですね！

4.コードの簡単な解説

今回は花の高さを配列に読み込みながら、花の高さを比較するようにしました

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
class Program
{
    static void Main(string[] args)
    {
        string temp = System.Console.ReadLine();
        int N = int.Parse(temp);
        string[] temp1 = System.Console.ReadLine().Split(' ');
        int[] H = new int[N];
        int plusnum = 0;
        for (int i = 0; i < N; i++)
        {
            H[i] = int.Parse(temp1[i]);
            if (i == 0) { plusnum = H[i]; }
            else if (i >= 1&&(H[i]-H[i-1])>0)
            {
                plusnum += H[i] - H[i - 1];
            }
        }
        Console.WriteLine(plusnum);
    }
}

5.最後に

自力で解答を出せたので、地力があがってきた…？(掛詞がうまい)

ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです！

【プログラミングコンテスト】AtCoder Beginner Contest 116③