c++ - 一维世界中到极点的平均距离

Question

我的世界

想象一个存在极点的一维离散世界。让我们用一个一维网格来表示这个世界，其中每个插槽包含一个极点 I 或不包含一个极点 -

--------I-I---------I----II-------I-------------I--

在这个世界上有 n 个插槽和 m 个极点。我们可以用一个长度为 m 的 vector 来表示这个世界，其中列出了极点的位置

std::vector<unsigned int> polePositions;

或使用长度为 n

的 bool vector

std::vector<bool> isThereAPole;

兴趣统计和示例

每个插槽到所有极点的平均距离 (averageDistance)。例如槽位索引2下方(从零开始计数)

---I-I

到两极的平均距离

averageDistance = (1 + 3) / 2 = 2

然后我们可以计算每个插槽的平均距离并将它们取平均以获得平均平均距离 (averageAverageDistance)。对于上面的例子，

averageAverageDistance = ((3 + 5) / 2 + (2 + 4)/2 + (1+3)/2 + (0+2)/2 + (1 + 1)/2 + (2+0)/2)/6 = 12/6 = 2

问题

如何高效地计算这个averageAverageDistance？

通常，每次调用该函数时，我都会有大约 n=1e6 个插槽和大约 m=1e5 个极点。 n 将在每次函数调用时保持不变，但 m(和 polePositions 或 isThereAPole)会因人而异函数调用。

实现不当

这里以上面的小数据为例，简单实现一下

#include <iostream>
#include <vector>
#include <math.h>

double getAverageAverageDistance(std::vector<unsigned int> polePositions, int n)
{
    double averageAverageDistance = 0.0;
    for (int slot = 0 ; slot < n ; slot++)
    {
        double averageDistance = 0.0;
        for (auto& polePosition : polePositions)
        {
               averageDistance += fabs(slot - polePosition);
        }
        averageDistance /= polePositions.size();
        averageAverageDistance += averageDistance;
    }
    averageAverageDistance /= n;
    return averageAverageDistance;
}

int main()
{
  std::vector<unsigned int> polePositions;
  polePositions.push_back(3);
  polePositions.push_back(5);
  int n = 6;

  std::cout << "averageAverageDistance = " << getAverageAverageDistance(polePositions, n) << "\n";
}

正确输出

averageAverageDistance = 2

这个程序的时间复杂度为 O(n·m)。有更好的解决方案吗？

Answer 1

下面是 6 个槽从头开始的问题。

假设所有槽都已满。然后，从每个槽到每隔一个插槽可以用 6 x 6 矩阵表示为:

| 0 1 2 3 4 5 |
| 1 0 1 2 3 4 |
| 2 1 0 1 2 3 |
| 3 2 1 0 1 2 |
| 4 3 2 1 0 1 |
| 5 4 3 2 1 0 |

总距离可以通过将所有数字相加并相除来计算总数减少了 36。

当一个槽没有装满一根柱子时，可以移除整根柱子。比如说，第二个插槽丢失了。您可以删除整个第二列以得到总和。当然，总和现在需要除以 30 和不是 36。

让我们来表示一列中所有数字的总和。叫它SUM(i) 其中 i 是列的索引。

当缺少第二行时，您可以将总和表示为:

SUM(0) + SUM(2) + ... + SUM(5)

幸运的是，总和有一个很好的模式，你可以表示SUM(i) 作为插槽总数和 i 的函数。

让我们看一下 N = 6 的列总和。

SUM(0) = 5*6/2

我们称基数和为CSUM。

SUM(1) 是通过从 CSUM 中减去 5 然后加 1 得到的。

SUM(1) = CSUM - (5-1)

SUM(2) 是从 CSUM 中去掉 5 和 4，然后加上 2 和 1 得到的。

SUM(2) = CSUM - (5-2) - (4-1)
=> SUM(2) = CSUM - (5-2) - (5-2)
=> SUM(2) = CSUM - 2*(5-2)

SUM(3) 是通过从 CSUM 中删除 5、4 和 3，然后向其添加 3、2 和 1 获得的。

SUM(3) = CSUM - (5-3) - (4-2) - (3-1)
=> SUM(3) = CSUM - (5-3) - (5-3) - (5-3)
=> SUM(3) = CSUM - 3*(5-3)

模式是:

SUM(i) = CSUM - i*((N-1) - i)

一般情况下，

CSUM = (N-1)*N/2

有了这些知识，如果您知道有极点的槽的索引。这是一个 O(M) 操作如果有是 M 极点。

---

演示程序:

#include <iostream>
#include <vector>

int SUM(int N, int p)
{
   return (N-1)*N/2 - p*((N-1) - p);
}

int main()
{
   int N = 0;
   int M = 0;

   std::cin >> N;
   std::cin >> M;

   std::vector<int> polePositions;
   for ( int i = 0; i < M; ++i )
   {
      int p;
      std::cin >> p;
      polePositions.push_back(p);
   }

   int s = 0;
   for ( int p : polePositions )
   {
      s += SUM(N, p);
   }

   double average = 1.0*s/(N*polePositions.size());

   std::cout << "Average: " << average << std::endl;
}

给定输入

6
2
3 5

输出是

Average: 2