-2

我正在尝试制作最有效的算法来解决通信船只的问题。

Input:
Number of vessels (int, 1-200000)
For each vessel - altitude of vessel (int, can be negative)
                  height (int, >1)
                  width (int, >1)
                  depth (int, >1)
Volume of water (int >=0, read to EOF)

Output:
Altitude of water surface (double) or "Empty" or "Overflow"

我做了一个程序（用 C 语言），它使用二分法，但有时不能给出正确的结果（fe 容器 1 1 1 1 和 3 3 3 3 和体积 1 给出 2.25 而不是 2.0，或者溢出检测问题） .

所以我的算法是：

  • 读取值
  • 转换它们(altitude of bottom, altitude of top, area)
  • qsort (altitude of bottom)
  • SURFACE = (lowest + highest place)/2
  • 从底部到计算体积SURFACE
  • 音量是否等于所需音量（允许错误 0.000001）？是大于还是小于所需体积？
  • 如果较大取下半部分并重复过程，如果较小取上半部分，则保存计算体积，重复过程。

我希望这是可以理解的。

有没有更好的方法来解决这个问题？或者如何改进我的方法？

输入图片：

输入图像

4

1 回答 1

1

如果系统中有相同的液体（因此容器中的液体密度相同） - 所有连通容器中的液位将相同。

Step 1.让我们计算一些不变的参数：实验前的液体体积和最低液位：

V before = SUM(H i *W i )，其中 H i是容器 i 的高度，W i是容器 i 的宽度。

L最低= MIN(A i + D i )，其中 A i是船舶 i 的高度，D i是船舶 i 的深度

基本方程将是储蓄量定律（在系统释放之前和之后）：

V之前= V之后+ V溢出

再加上必须满足以下明显条件：

V溢出> 0 如果 L结果> L最低

V溢出= 0 如果 L结果<= L最低

在此基础上，我们可以设置第一级，例如，作为前级的算术平均值，然后计算差值，检查V溢出，如果不满足条件，则增加和减少级别并重复。

第 2 步。 但我有另一个想法。让我们检查一下系统即将溢出的情况：

V溢出= 0

L结果= L最低

V after = SUM((L result - A i )*W i )，但当然对于那些 i where (L result - A i ) > 0 因为显然容器不能容纳负量的液体。

因此，我们将有三种可能的情况：

如果 V after = V before，那么 L结果就是我们要找的。

如果 V after > V before，则没有发生溢出，并且发生了容器之间的简单液体重新分配。因此，我们可以将结果级别计算为：

L结果= V之前/SUM(W i )，对于那些 i 其中 (L结果- A i ) > 0

如果 V after < V before，则发生溢出并且 L结果= L最低。V before - V after从最低容器的开口端离开系统的差值。

于 2013-11-10T10:32:03.450 回答