c++ - 最小限の動きでボックスを交換します

Question

これは（終了した）プログラミングコンテストからの質問です。私はこの問題を解決するのに苦労していましたが、それを解決するための健全な方法を見つけることができませんでした。

質問は次のとおりです。

IIITアラハバードは、毎年10月1日から5日までTechno-Cultural FiestaEffervescenceMM12を祝っています。シェフは、このお祭りシーズンにキャンディーを供給することに同意しました。シェフは、1からNまでの番号が付けられたN箱のキャンディーを用意しました（各番号は1回だけ発生します）。シェフは箱の配置に非常にこだわっています。彼は箱を特定の順序で並べたいと思っていますが、残念ながらシェフは忙しいです。彼はあなたに彼のために箱を並べ替えるように頼んだ。ボックスの現在の順序を考えると、指定された順序でボックスを再配置する必要があります。ただし、制限があります。必要な順序を実現するには、隣接する2つのボックスのみを交換できます。出力、必要なそのような隣接するスワップの最小数。

入力

入力の最初の行には、単一の整数T、テストケースの数が含まれています。各テストケースには3行が含まれ、最初の行には1つの整数N、ボックスの数が含まれます。次の2行にはそれぞれN個の数字が含まれ、最初の行は指定されたボックスの順序で、2番目の行は必要な順序です。

出力

テストケースごとに、必要な隣接スワップの最小数である単一の整数「K」を出力します。制約：

1<=T<=10
1<=N<=10^5

例

入力：

4

3
1 2 3
3 1 2

3
1 2 3
3 2 1

5
3 4 5 2 1  
4 1 5 2 3  

4
1 2 3 4
2 3 4 1

出力：

2
3
6
3

私はこの質問についてほとんど無知でした。誰かが質問の背後にある論理を説明できますか？

Answer 1

問題は、配列内の反転をカウントする、非常に「古典的な」競技プログラミングの問題です。反転は、ペア（i、j）として定義されます。ここで、i<jおよびA[i]>A[j]です。

任意の数の配列が与えられ、転倒の数を数えるように求められる最も一般的なバージョンには、マージソートアルゴリズムを変更することによるO（n log n）ソリューションがあります。

配列の最大値に妥当な上限がある（これは配列の長さではないことに注意してください）、より制限されたバージョン^は、O（n log m）で解くことができます。ここで、mは最大値です。配列内。ここでの主なポイントは、作成する必要のあるコードの量がマージソートアプローチよりもはるかに少ないことです。

問題の問題は、配列を特定の順序に並べ替えるためのスワップの数を数えることです。これは、配列を昇順で並べ替えるためのスワップの数を数えることとして再構築でき、要約すると、反転の数を数えます。なぜ反転の数？2つの隣接する要素を交換するごとに、最大で1つの反転しか解決できないためです。

最終設定に対するボックスの現在の位置を説明する配列を作成する必要があります。次に、アルゴリズムを開始できます。

1. 長さm（問題の問題の場合はm = n）のフェニックツリー（バイナリインデックスツリー）を構築します。

   フェニックツリーを使用して、現在の要素よりも大きい配列内の先行する要素の数を数えるのに役立てます。これまでに遭遇した数値の頻度を維持し、フェニックツリー範囲合計クエリを使用して、現在の要素より少ない要素の数を取得します（そして現在の要素よりも大きい要素の数を導き出します）。

2. 配列のn個の要素をループします。

   • 範囲合計クエリを使用して、現在の数よりも小さい数が記録されている数をカウントします。
   • 上記の情報を使用して、現在の数よりも大きい数を確認してください。これを反転カウントに追加します。考慮されている要素を含めないように注意してください。（*）
   • 要素の値でFenwickTreeに+1を調整します。

3. （*）ステップで累積される反転カウント。

^質問は、要素が一意であることを明確に示しているため、上記のアルゴリズムが機能します。一意性が必要な条件であるかどうか、または繰り返し要素がある場合に対応するようにアルゴリズムを変更できるかどうかはわかりません。

Answer 2

ソースリストを（1,2、...、N）の順列に減らします。（ターゲットの逆をソースに適用することによって）

次に、反転の数を数えます。

すなわち

vector<int> source = ...;
vector<int> target = ...;

vector<int> inv(N)

for (int i = 0; i < N; i++)
   inv[target[i]] = i;

vector<int> perm(N);

for (int i = 0; i < N; i++)
    perm[i] = source[inv[i]];

次に、標準アルゴリズムを使用して、permの反転をカウントします。

Answer 3

目的の順序が番号の並べ替えられた順序であると仮定すると、問題は配列内の反転の数を見つけることになります。

との場合、Apair (i,j)は反転であると言われます。これは、隣接する要素間の（最適な）スワップごとに、反転の数が正確に減少するためです。マージソートと非常によく似た分割統治アルゴリズムによって、転倒の数を見つけることができます。これがCコードの良い説明です。i < jarray[i] > array[j]1O(n log n)

反転の数がスワップの最適な数に等しいことを証明します。

の任意iの位置にしarrayます。スワップarray[i]しarray[i+1]、反転の数を最大1つ減らします。したがって、必要なスワップの数は、少なくとも反転の数と同じです。一方、ソートされていない場合は、常に次のようarrayなペアを見つけることができ（つまり、反転）、と交換することで反転の数を1つ減らすことができます。したがって、反転の数はスワップの最小数に等しくなります。(i, i+1)array[i] > array[i+1](i,j)array[i]array[i+1]

Answer 4

この問題は、次のように反転カウントの問題と見なすことができます。

番号の優先順位が与えられているので、つまり、ソートすることになっている順序で。

優先順位を考慮し、それを数字に置き換えます

例えば：

3 4 5 2 1  
4 1 5 2 3  

上記のテストケースでは、4に優先度1が割り当てられ、1に優先度2が割り当てられ、5に優先度3が割り当てられていることがわかります。では、元のリストの番号をこれらの優先順位に置き換えてみませんか

つまり、元のリストを変換します

(3 4 5 2 1) to (5 1 3 4 2) 

（上記のように番号をそれぞれの優先順位に置き換えるだけです）

今、私たちのリストはに変わりました

5 1 3 4 2

昇順で並べ替えるだけです。

現在、隣接するスワップのみが許可されています。つまり、バブルソートにある程度関連しています。

バブルソートに必要なスワップの数。これは、現在の要素よりも小さい各要素の右側にある要素の数の合計に等しくなります。

例：リスト内

5 1 3 4 2

5の右側には、5よりも小さい4つの要素があります。

1の右側には、1より小さい要素が0個あります。

3の右側には、3よりも小さい1つの要素があります。

4の右側には1より小さい要素が1つあります。

2の右側には2より小さい要素が0個あります。

これで、最終的な答えは（4 + 0 + 1 + 1 + 0）=6になります。

これで、上記の手順は、ここで説明されている反転カウントを使用して計算できます http://www.geeksforgeeks.org/archives/3968。

注：私が得た答えは、全体を詳細に説明するだけで、非常に役に立ちました。ありがとうございました

Answer 5

これを数学的に証明することはできませんが、テストケースの4/4では、ボックスを左端から始めて右に移動することで、最小のスワップを取得します。つまり

3 4 5 2 1 //First get the 4 in the right place
4 3 5 2 1 //Done.  Now get the 1 in the right place
4 3 5 1 2
4 3 1 5 2
4 1 3 5 2 //Done.  Now the 5
4 1 5 3 2 //Done.  Now the 2
4 1 5 2 3 //All done.

したがって、このアルゴリズムは、特定の入力の最小値を提供するように見えます。一般的に最悪のケースは逆転のように見え、N *（N-1）/ 2スワップが必要になります（例2を参照）。