5

これは、あるプログラミング コンテストからの質問です (どのプログラミング コンテストに属しているか正確にはわかりません。1 年前に見ました)。質問は次のとおりです。

N 個の建物があり、それぞれに独自の高さがあります (一意であるとは限りません)。

{h1,h2,h3,...,hn}

同じ高さのすべての建物に h を言わせる必要があります。

許可される操作は次のとおりです。

  1. 建物に高さを加えることができます。
  2. 建物の高さをいくらか取り除くことができます。

ユニットの高さを削除/追加するには、各建物に関連するコストがかかります。c(i) を建物の単位高さを削除/追加するコストとします。それぞれの費用は次のとおりです。

{c1,c2,c3,...,cn}

十分な高さ (ユニット) が利用可能であると仮定すると、すべての建物を同じ高さにするために必要な最小コストを見つける必要があります。

入力: 最初の行は、建物の数 N を指定します。(1<=N<=100000)。入力の 2 行目は建物の高さです。

{h1,h2,h3,...,hn}

入力の 3 行目は、コスト配列を示します

 {c1,c2,c3.....,cn}

出力

出力は単に必要な最小コストになります。

サンプル入力:

3

2 1 3

10 1000 1

サンプル出力

12

説明: すべての建物の高さを 1 にすると、コストは 10*(2-1) + 1000*(1-1) + 1*(3-1)、つまり 12 になります。

O（n ^ 2）であるブルートフォースフォースメソッドを知っています。

私が考えた力ずくの方法は次のとおりです。

共通の高さ h が何であれ、それは

 {h1,h2,h3,....,hn}

つまり、 h は h(i) のいずれかに等しくなければなりません。各 h(i) をチェックすると、O(n^2) で答えを計算できます。

より速くすることは可能ですか？

4

2 に答える 2

2

O（n log（n））解決策：

h（i）がi番目の建物の高さを表し、c（i）がi番目の建物のコストを表すとします。

  1. ステップ-1：それぞれの建物の高さに従って建物を降順で並べ替えます。この配置をPと呼びます。つまり、P（1）は最大の建物の高さであり、P（n）は最小の建物の高さです。これはO（n log n）を取ります。
  2. ステップ-2：建物のすべての高さを合計します。Sがこの合計を表すとします。このステップにはO（n）時間がかかります。
  3. ステップ-3：Cost_of_Increase（i）が、SORTED ARRAY Pのi番目の建物の高さと等しいi番目の建物よりも低い高さのすべての建物の高さを作成する場合のコストを示します。つまり、Cost_of_Increase（i）を作成する場合建物P（i-1）、P（i-2）、... P（n）はP（i）番目の建物の高さに等しい。

次に、この再帰を使用します。

Cost_of_Increase（i）= Cost_of_Increase（i-1）+（h（i）-h（i-1））*（P（i-1）番目の建物からP（n）番目の建物までのコストの合計）

上記の再帰では、iとi-1の順序はPの順序、つまりソートされた順序に従っていることに注意してください。

ここで、Cost_of_decrease（i）が、i番目の建物よりも高い高さのすべての建物をSORTED ARRAY Pのi番目の建物の高さに等しくした場合のコストを示します。つまり、建物をP（1 ）、P（2）、... P（i-2）、P（i-1）はP（i）番目の建物の高さに等しい。

このために、この再帰を使用します。

Cost_of_decrease（i）= Cost_of_decrease（i + 1）+（h（i + 1）-h（i））*（P（1）番目の建物からP（i-1）番目の建物までのコストの合計）

したがって、すべての建物の高さをP（i）番目の建物と等しくするための総コストは次のとおりです。

Cost_of_Increase（i）+ Cost_of_decrease（i）。

すべての建物についてこれを取得したら、コストが最も小さい建物を確認するだけで、それが答えになります。

それが役に立てば幸い ！

于 2012-09-24T07:09:59.203 に答える
1

アルゴリズムの終了後に、すべての建物の高さに対して三分探索を行うか、ヒル クライミングアルゴリズムを使用します。高さごとに線形時間でコストを計算できるため、全体的な複雑さは O(N * log(H)) になり、H は可能な最大高さになります。

編集：これはあなたのために働くはずの疑似コードスニペットです（これは山登りのようなアプローチです）

  typedef long long ll;
  ll get_cost(int h) {
    if (h < 0 || h > MAX_HEIGHT) {
      return MAX_VAL; // some unreachable positive value
    }
    ...
  }


  int main() {
    ...
    int current = 0;
    int leftp, rightp;
    ll cv, lv, rv;
    ll step = SOME_BIG_ENOUGH_VALUE;
    while (step > 0) {
      leftp = current - step;
      rightp = current + step;
      cv = get_cost(current);
      lv = get_cost(leftp);
      rv = get_cost(rightp);
      if (cv <= rv && cv <= lv) {
        step /= 2;
      } else if (lv < rv) {
        current = leftp;
      } else {
        current = rightp;
      }
    }
    ...
  }
于 2012-09-24T06:58:16.610 に答える