algorithm - 给定一个最佳拟合大小的数组，告诉其他数组可以拟合多少个元素(下面有更多详细信息)

Question

There is an old dry well. Its sides are made of concrete rings. Each such ring is one meter high, but the rings can have different (internal) diameters. Nevertheless, all the rings are centered on one another. The well is N meters deep; that is, there are N concrete rings inside it. You are about to drop M concrete disks into the well. Each disk is one meter thick, and different disks can have different diameters. Once each disk is dropped, it falls down until:

• it hits the bottom of the well;
• it hits a ring whose internal diameter is smaller then the disk's diameter; or
• it hits a previously dropped disk. (Note that if the internal diameter of a ring and the diameter of a disk are equal, then the disk can fall through the ring.)

The disks you are about to drop are ready and you know their diameters, as well as the diameters of all the rings in the well. The question arises: how many of the disks will fit into the well?

Write a function: int falling_disks(int A[], int N, int B[], int M); that, given two zero-indexed arrays of integers − A, containing the internal diameters of the N rings (in top-down order), and B, containing the diameters of the M disks (in the order they are to be dropped) − returns the number of disks that will fit into the well. For example, given the following two arrays:

      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

the function should return 4, as all but the last of the disks will fit into the well. The figure shows the situation after dropping four disks.

Assume that:

• N is an integer within the range [1..200,000];
  • M is an integer within the range [1..200,000];
  • each element of array A is an integer within the range [1..1,000,000,000];
  • each element of array B is an integer within the range [1..1,000,000,000].

Complexity:

• expected worst-case time complexity is O(N);
  • expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
  • Elements of input arrays can be modified.

我尝试使用堆栈并执行某些操作，但是我无法获得O(n)解决方案，即使我认为进行了一些优化，最坏的情况仍然是O(n ^ 2)。

Answer 1

首先，您需要修改环的给定内径以填充不必要的间隙。假设您在一个内径为5的环下面有一个内径为2的环。任何大于2的磁盘都将无法到达该环。因此，我们可以将下环的内径更改为2。基本上，我们正在填补空白。

前:

后:

使用以下算法:

min = A [0]

我= 1

如果i == N，则停止

如果A [i]

如果A [i]> min，则A [i] =最小

i++

转到步骤3

既然这些环已经形成了一个结构，其中每个下环的内径都小于或等于上环的内径，那么下一部分就相当简单了。我们将从底部开始插入磁盘。如果第一个圆盘适合最低的圆环，则可以，否则，我们继续移动到其上方的圆环，依此类推。您可以使用如下算法:

i = N-1

j = 0

如果i <0或j == M，则停止

如果A [i]> = B [j]，则j++

我-

转到步骤3

变量 j的最终值是必需的答案。