1

問題を解決するためのアルゴリズムを定式化しようとしています。この問題では、いくつかの建物を含む写真があります。写真は n 個の縦方向の領域 (ピースと呼ばれる) に分割され、各ピースの建物の高さが与えられます。

1 つの建物は複数の連続するピースにまたがることができますが、各ピースには目に見える建物が 1 つしか含まれないか、建物がまったく含まれない場合があります。建物の最小数を見つける必要があります。

例えば与えられた、

3 (ピース数)

1 2 3 (高さ) ans = 3

3

1 2 1 ans = 2

6

1 2 3 1 2 3 ans = 5 (オーバーラップを示すのに役立つ図)。

わかったような気がしますが、しっかりしたアルゴリズムを手に入れることができません。何か案は？

4

1 に答える 1

0

指定された配列から最小の数値を見つけ、この数値のすべての発生を説明できます。これにより、配列が複数のサブ配列に分割され、それぞれの問題を再帰的に解決する必要があります。

例では：

1 2 3 1 2 3 (total = 0)

最小数は 1 です。

x 2 3 x 2 3 (total = 1)

これで、2 つのサブアレイができました。最初のものを解きます - 最小の数は 2 です:

  x 3       (total = 2)

最後に、1 つの要素が得られます: total = 3 他の部分配列を解くと、5 になります。

C# のコードを次に示します。

int Solve(int[] ar, int start, int end){
    //base for the recursion -> the subarray has single element
    if(end-start == 1) return 1;

    //base for the recursion -> the subarray is empty
    if(end-start < 1) return 0;

    //find min
    int m = int.MaxValue;
    for(int i = start; i < end; i++)
        if (ar[i] < m) m = ar[i];

    int total = 1;
    //find the subarrays and their contribution recursively
    int subStart = start;
    for(int subEnd = start; subEnd < end; subEnd++){
        if(ar[subEnd] == m) {
            total += Solve(ar, subStart, subEnd);
            subStart = subEnd + 1;
        }
    }
    total += Solve(ar, subStart, ar.Length);

    return total;
}
于 2012-06-10T06:09:10.360 に答える