Find the height of the water needed to flood the landscape to a certain volume

Question

Recently, I ran into an algorithmic problem, the purpose of which was to calculate the height of the water level needed to create a certain amount of floods in a city with buildings, each of which has a width of 1.

This is somewhat similar to the two-dimensional rainwater capture problem described here:

The maximum volume of flooded rainwater in 3D

However, in my problem, we are counting the water above the buildings in addition to the water locked between the buildings. For example, take this instance of the problem:

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

This means that we must calculate the required water level so that a city with buildings 30, 40 and 20 high in this order has a water flow of at least 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

. , . - O (n log n), builidings. 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;
}

Answer 2

, , , , , , , .

Answer 3

, . , .

, , 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), . O(n log n). O(n log n + n) , O(nm), m .

#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 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 4

Binary search by answer to find the correct height. Guess the height and find the volume above the buildings, if it is more than desire, guess lower, if it is less than the desired value, guess higher. Continue this procedure until you find the correct height.