找出将景观淹没到一定体积所需的水的高度

Question

我最近遇到了一个算法问题，目标是计算在一个建筑宽度为1的城市中产生一定洪水所需的水位高度。

这有点类似于此处描述的二维雨水收集问题：

三维截留雨水的最大体积

然而，在我的问题中，除了建筑物之间的水之外，我们还计算建筑物上方的水。例如，以这个问题为例：

volume needed: 60
number of buildings: 3
heights of buildings: 30 40 20

这意味着我们必须计算所需的水位，这样一个建筑高度为30、40和20的城市，其水量至少为60。

^
|
50       |~~~~~~~~~~~~~|
|        |             |        
40       |    -----    |                
|        |    |   |    |                 
30       -----|   |    |               
|        |   ||   |    |        
20       |   ||   |-----
|        |   ||   ||   |
10       |   ||   ||   |
|        |   ||   ||   |
.----------1----2----3---------->

在这种情况下，结果为50，因为水位需要在50的高度，以便建筑物之间和上方的水量至少为60。在这里，每栋建筑上方的洪水分别为20、10和30，加起来正好是60。

我的尝试在时间和正确性方面都表现不佳：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
  int v;
  int n;
  cin >> v >> n;

  vector<int> altitudes;
  int count = 0;
  int altitude;

  while (count < n) {
    cin >> altitude;
    altitudes.push_back(altitude);
    count++;
  }

  sort(altitudes.begin(), altitudes.end());

  int vtemp = 0;
  int i = 1;
  int h = altitudes[0];

  while (vtemp < v && i < n) {
    h++;
    if (h == altitudes[i]) {
      i++;
    }
    vtemp = 0;
    for (int j = 0; j < i; j++) {
      vtemp += h - altitudes[j];
    }
  }

  cout << h << endl;

  return 0;
}

Answer 1

当你对建筑物进行分类时，你走在了正确的轨道上。这让我们更清楚地了解每栋建筑上方被困的水层。

例如，假设我们有高度4, 2, 3, 1, 2, 5的建筑物：

     x
x    x
x x  x
xxx xx
xxxxxx

让我们用水把他们淹没。此图使用1表示最底层的水，2表示次底层的水，依此类推：

44444x
x3333x
x2x22x
xxx1xx
xxxxxx

我们可以逐行遍历建筑物以增加水层，直到达到所需的体积。但是，这需要O（nm）时间，其中n是建筑物的数量，m是最大建筑物高度。我们可以做得更好。

让我们把建筑物分类。现在，从左到右的高度为1、2、2、3、4、5：

     x
    xx
   xxx
 xxxxx
xxxxxx

再一次，让我们淹没他们：

44444x
3333xx
222xxx
1xxxxx
xxxxxx

现在水层更容易计算。每层的长度是相同高度的建筑数量加上上上一层的长度。

这使我们能够在时间上计算层数，因为我们扫描了一次建筑高度，并对每个建筑执行了固定数量的操作。对建筑物进行排序的成本为O（n log n）。除非m非常小，否则O（n log n n）的总成本优于O（nm）。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
  int requiredVolume, n;

  cin >> requiredVolume >> n;
  vector<int> heights;
  for (int i = 0; i < n; ++i) {
    int height;
    cin >> height;
    heights.push_back(height);
  }

  // Sort the buildings by increasing height.
  sort(heights.begin(), heights.end());

  // Start with the required volume and subtract layers until we reach zero.
  int volume = requiredVolume,
      waterHeight = heights[0],
      layerLength = 0,
      pos = 0;

  while (volume > 0) {
    // Look for the next building that's taller than the current one.
    int seek = pos;
    while (seek < n && heights[seek] == heights[pos]) {
      ++seek;
    }

    // Extend the current water layer.
    layerLength += seek - pos;

    // Calculate the number of layers we would need to reach zero.
    int needLayers = (volume + layerLength - 1) / layerLength;

    // If we're at the tallest building, take all the layers we need.
    // Otherwise, take layers up to the height of the next building.
    int addLayers; 
    if (seek == n) {
      addLayers = needLayers;
    } else {
      addLayers = min(heights[seek] - heights[pos], needLayers);
    }

    volume -= addLayers * layerLength;
    waterHeight += addLayers;

    cout << "with water at height " << waterHeight <<
        ", the volume is " << (requiredVolume - volume) << '\n';

    // Advance to the next building.
    pos = seek;
  }

  cout << "final answer:\n    minimum height = " << waterHeight <<
      ", volume reached = " << (requiredVolume - volume) << '\n';

  return 0;
}

对于您在问题中给出的问题实例：

60 3
30 40 20

我们得到以下输出：

with water at height 30, the volume is 10
with water at height 40, the volume is 30
with water at height 50, the volume is 60
final answer:
    minimum height = 50, volume reached = 60

如果我们想通过上面示例中的建筑物实现至少11的体积：

11 5
4 2 3 1 2 5

我们得到：

with water at height 2, the volume is 1
with water at height 3, the volume is 4
with water at height 4, the volume is 8
with water at height 5, the volume is 13
final answer:
    minimum height = 5, volume reached = 13

Answer 2

将高度从最低到最高排序，然后开始填充最低的，直到其高度等于第二个最低的，然后填充最低的和第二个最低的，直到其高度等于第三个最低的，依此类推，直到水用完。

Answer 3

我在算法中添加了代码注释。我在你的测试数据上进行了测试，效果很好。时间复杂度为O（n log n），因为我们需要对建筑进行排序。没有排序，算法在O（n）中工作

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int v;
    int n;
    cin >> v >> n;

    vector<int> altitudes;
    int count = 0;
    int altitude;

    while (count < n) {
        cin >> altitude;
        altitudes.push_back(altitude);
        count++;
    }

    sort(altitudes.begin(), altitudes.end());
//-- changed from here
    int current_level = altitudes[0]; //start from height of the smallest building
    int length = 0;

    while (v > 0)
    {
        ++length; //go to next level
        for (; length < altitudes.size() && altitudes[length] == altitudes[length - 1]; ++length); //find length of current water level

        int height = v / length; //maximum possible height to fill
        if (length < altitudes.size()) //if not all building in use
            height = min(height, altitudes[length] - current_level); //fill with all water (height) or with the difference to next level

        current_level += height; //increase level by height
        v -= height * length; //decrease amount of water

        if (length == altitudes.size() || v < length) //we filled the whole area, or there is no enough water to fill 1 'meter'
            break;
    }

    cout << current_level << endl;

    return 0;
}