9

古いドライウェルがあります。その側面はコンクリートのリングで作られています。このような各リングの高さは1メートルですが、リングの直径は異なる場合があります。それにもかかわらず、すべてのリングは互いに中心にあります。井戸の深さはNメートルです。つまり、その中にN個のコンクリートリングがあります。M個のコンクリートディスクを井戸に落とそうとしています。各ディスクの厚さは1メートルで、ディスクごとに直径が異なる場合があります。各ディスクがドロップされると、次の状態になるまでフォールダウンします。

  • それは井戸の底に当たります。
  • 内径がディスクの直径よりも小さいリングに当たります。また
  • 以前にドロップされたディスクにヒットします。（リングの内径とディスクの直径が等しい場合、ディスクがリングを通り抜ける可能性があることに注意してください。）

ドロップしようとしているディスクの準備ができており、それらの直径と、ウェル内のすべてのリングの直径がわかっています。疑問が生じます：何枚のディスクが井戸に収まるでしょうか？

関数を記述します：intfalling_disks（int A []、int N、int B []、int M）; つまり、整数の2つのゼロインデックス配列が与えられた場合-AはNリングの内径を含み（上から下の順序）、BはMディスクの直径を含みます（ドロップされる順序で）-ウェルに収まるディスクの数を返します。たとえば、次の2つの配列があるとします。

      A[0] = 5    B[0] = 2
      A[1] = 6    B[1] = 3
      A[2] = 4    B[2] = 5
      A[3] = 3    B[3] = 2
      A[4] = 6    B[4] = 4
      A[5] = 2
      A[6] = 3

最後のディスクを除くすべてがウェルに収まるため、関数は4を返す必要があります。この図は、4つのディスクをドロップした後の状況を示しています。 ここに画像の説明を入力してください

と仮定する：

  • Nは[1..200,000]の範囲内の整数です。
    • Mは[1..200,000]の範囲内の整数です。
    • 配列Aの各要素は、[1..1,000,000,000]の範囲内の整数です。
    • 配列Bの各要素は、[1..1,000,000,000]の範囲内の整数です。

複雑：

  • 予想される最悪の場合の時間計算量はO（N）です。
    • 予想される最悪の場合のスペースの複雑さは、入力ストレージを超えたO（N）です（入力引数に必要なストレージはカウントされません）。
    • 入力配列の要素は変更できます。

スタックを使用して何かを実行しようとしましたが、O（n）ソリューションに到達できません。いくつかの最適化を行った後でも、最悪のケースはO（n ^ 2）のままです。

4

6 に答える 6

15

最初に、指定されたリングの内径を変更して、不要なギャップを埋める必要があります。5内径のリングの下に内径 のリングがあるとします2。より大きいサイズのディスクは、2そのリングに到達できません。したがって、下のリングの内径を に変更できます2。基本的に、ギャップを埋めています。

前：

埋められていないギャップ

後：

埋められたギャップ

次のアルゴリズムを使用します。

  1. 最小 = A[0]
  2. 私は= 1
  3. i == N の場合は停止
  4. A[i] < 最小の場合、最小 = A[i]
  5. A[i] > 最小の場合、A[i] = 最小
  6. i++
  7. 手順 3 に進みます

リングは、各下部リングが上部リングの内径以下の内径を持つ構造を形成したので、次の部分はかなり単純です。ディスクは下から挿入していきます。最初のディスクが一番下のリングに収まる場合は問題ありません。それ以外の場合は、その上のリングに移動します。次のようなアルゴリズムを使用できます。

  1. 私は= N-1
  2. j = 0
  3. i < 0 または j == M の場合、STOP
  4. A[i] >= B[j] の場合、j++
  5. 私 -
  6. 手順 3 に進みます

変数の最終値jは、必要な答えです。

于 2013-01-11T23:08:30.133 に答える
5 
public static int falling_disks(int[] A, int[] B)
{
    int mymin = A[0];
    int nbDisk = 0;

    for (int i = 0; i < A.Length; i++)
    {
        if (A[i] < mymin) mymin = A[i];
        if (A[i] > mymin) A[i] = mymin;               
    }             

    for (int i = A.Length - 1; i >= 0; i--) 
    {
        if (B[nbDisk] <= A[i]) nbDisk++;
        if (nbDisk == B.Length) break;
    }           

    return nbDisk;
 }
于 2013-02-27T23:51:53.210 に答える
4

実はとても簡単です。まず、ウェルの上部から移動して、到達できないスペースを削除する必要があります（これまでのところA [x]を最小に設定してください）。

例

2つ目は、ウェルの底からディスクが収まる場合はディスクを配置することです。

于 2013-01-11T20:40:36.323 に答える
1

少し最適化... O（N）で実行される一般的なソリューションで、それは正しいです。

B 配列の最初のディスクの値が A 配列の最初の直径の < である場合、A 配列の最初の調整 (ドライウェルを表す) を実行せずに、すぐに 0 を返すことができます。

于 2013-04-01T15:48:40.787 に答える
0

壊れやすい周囲の素材を最初の円盤に取り付け、落下すると折れてしまうことを想像してみてください。

この壊れやすい円盤が深さ k に達したときの幅を配列 A[k] に記録します。

これは、最初のディスクの落下をシミュレートすることにより、O(n) で実行できます。

次のディスクでは、前のディスクに着陸するか、以前の深さで停止します。現在の深度の A[k] が次のディスクのサイズよりも小さい場合にのみ、以前の深度で停止します。

したがって、後続のディスクを配置するためのアルゴリズムは次のとおりです。

  1. 現在の深度を 1 減らす
  2. 現在の深度が 0 の場合、ウェルは STOP で満たされています
  3. A[現在の深さ] が現在のリングの幅より小さい間、ステップ 1 に進みます
  4. 次のリングに移動し、ステップ 1 に進みます

現在の深さはループごとに減少するため、完了するまでに O(n) ステップが必要です。

于 2013-01-11T20:38:44.693 に答える