9

有一口老干井。它的侧面由混凝土环制成。每个这样的环都有一米高，但这些环可以有不同的（内）直径。然而，所有的环都以彼此为中心。井深N米；也就是说，里面有N个混凝土环。您即将将 M 个混凝土圆盘放入井中。每个圆盘厚一米，不同的圆盘可以有不同的直径。一旦每个磁盘掉落，它就会掉落，直到：

  • 它撞到井底；
  • 它撞击一个内径小于圆盘直径的环；或者
  • 它击中了先前掉落的磁盘。（请注意，如果环的内径和圆盘的直径相等，则圆盘可以穿过环。）

您将要掉落的圆盘已准备好，您知道它们的直径，以及井中所有圆环的直径。问题出现了：有多少磁盘可以放入井中？

写一个函数：int fall_disks(int A[], int N, int B[], int M); 即，给定两个零索引的整数数组 - A，包含 N 个环的内径（按自上而下的顺序），B，包含 M 个圆盘的直径（按它们被丢弃的顺序） -返回将适合井的磁盘数。例如，给定以下两个数组：

      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，因为除了最后一个磁盘之外的所有磁盘都可以放入井中。该图显示了丢弃四个磁盘后的情况。 在此处输入图像描述

假使，假设：

  • 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] < min 那么 min = A[i]
  5. 如果 A[i] > min 那么 A[i] = min
  6. 我++
  7. 转到第 3 步

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

  1. 我 = N-1
  2. j = 0
  3. 如果 i < 0 或 j == M 则停止
  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] 设置为最小值）。

例子

第二件事就是从井底取出合适的圆盘。

于 2013-01-11T20:40:36.323 回答
1

一点优化......在O（N）中执行的一般解决方案上是正确的。

如果 B 阵列中第一个磁盘的值小于 A 阵列中的第一个直径，您可以立即返回 0 而无需执行 A 阵列的第一次调整（代表干井）。

于 2013-04-01T15:48:40.787 回答
0

想象一下，将易碎的周围材料连接到第一个圆盘上，该圆盘会在它下落时折断。

在数组 A[k] 中记录这个易碎圆盘到达深度 k 时的宽度。

这可以通过模拟第一个磁盘的下降在 O(n) 中完成。

对于下一个磁盘，我们要么降落在前一个磁盘上，要么停在较早的深度。当且仅当当前深度的 A[k] 小于下一个磁盘的大小时，我们才会停在较早的深度。

所以放置后续磁盘的算法是：

  1. 将当前深度减少 1
  2. 如果当前深度为 0，那么我们已经填满了井 STOP
  3. 当 A[当前深度] 小于当前环的宽度时转到第 1 步
  4. 移动到下一个环并转到第 1 步

当前深度在每个循环上都会递减，因此这需要 O(n) 步才能完成。

于 2013-01-11T20:38:44.693 回答
0 
  class Program
{
    static void Main(string[] args)
    {
        int []A= new int[] {5,6,4,3,6,2,3};
        int[] B = new int[] { 2, 3, 5, 2, 4 };
       // Array.Reverse(A);

        Program obj = new Program();
        obj.NoOfDisc(A,B);

    }

    public void NoOfDisc (int[] A, int[] B)
    {
        int i;
        int count= 0;
     int   n= (A.Length)-1;
     for (i = 0; i < A.Length; i++)
     {
         if (n >= 0)
         {

             if (B[i] < A[n])
             {
                 count = count + 1;
                 A[n] = B[i];
                 n = n - 1;
             }

             else
             {
                 i = i - 1;
                 n = n - 1;
             }
         }
     }

   Console.WriteLine(count);
   Console.ReadLine();
  // return count;
    }
}
于 2013-06-26T08:56:27.717 回答