-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.0 ではなく 2.25 を返す、またはオーバーフロー検出の問題)。 .

だから私のアルゴリズムは次のとおりです。

  • 読み取り値
  • それらを変換する(altitude of bottom, altitude of top, area)
  • qsort (altitude of bottom)
  • SURFACE = (lowest + highest place)/2
  • 下から下までの体積を計算するSURFACE
  • ボリュームは目的のボリュームと同じですか (エラー 0.000001 を許可)? 希望のボリュームよりも大きいか小さいか?
  • 大きい場合は下半分を取り、プロセスを繰り返します。小さい場合は上半分を取り、計算されたボリュームを保存し、プロセスを繰り返します。

理解できることを願っています。

これを解決するためのより良い方法はありますか? または、私の方法を改善する方法は？

入力の画像:

入力イメージ

4

1 に答える 1

1

システム内に同じ液体がある場合（容器内の液体の密度が同じである場合）、通信しているすべての容器のレベルは同じになります。

ステップ 1.いくつかの変更されないパラメーターを計算しましょう: 実験前の液体の量と最低レベル:

V before = SUM(H i *W i )、ここで、H iは血管 i の高さ、W iは血管 i の幅です。

L low = MIN(A i + D i )、ここで、A iは船舶 i の高度、D iは船舶 i の深さ

基本的な方程式は、ボリュームを保存する法則です (システムが解放される前と後):

V before = V after + Vオーバーフロー

さらに、次の明白な条件が満たされている必要があります。

L結果> L最低の場合、 Vオーバーフロー> 0

L結果<= L最低の場合、 Vオーバーフロー= 0

それに基づいて、たとえば、最初のレベルを前のレベルの算術平均として設定し、差を計算して Vオーバーフローを確認し、条件を満たさない場合はレベルを増減して繰り返すことができます。

ステップ 2. しかし、私には別の考えがあります。システムがちょうどオーバーフローしている場合を確認してみましょう。

Vオーバーフロー= 0

L結果= L最低

V after = SUM((L result - A i )*W i ) ですが、もちろん、(L result - A i ) > 0 の場合は、容器は負の量の液体を保持できないためです。

その結果、次の 3 つのケースが考えられます。

V after = V beforeの場合、L resultが探しているものです。

V after > V beforeの場合、オーバーフローは発生せず、容器間の液体の単純な再配分が発生しました。したがって、結果レベルは次のように計算できます。

L result = V before /SUM(W i ) ((L result - A i ) > 0の場合の i について)

V after < V beforeの場合、オーバーフローが発生し、L結果= L最小。V before - V afterの差は、最も低い容器の開放端からシステムを出ました。

于 2013-11-10T10:32:03.450 に答える