2

これは、オンライン筆記試験からの質問の1つです。

（1 ... N）から番号が付けられた本が倉庫に到着しました。

本「i」が本「i+1」の左側にのみ存在し（すべてのiについて、1 <= i <= N-1）、その本Nが本1の左側。[​​はい！循環的にソートされたシーケンスが最適な配置です]

受け取った本はランダムな順序になっています。今、あなたの仕事は、上記の最良の配置を達成するために必要な最小限の動きを見つけることです。

有効な移動は、隣接する本のペアを選択して場所を切り替えることだけであることに注意してください。

たとえば、本が最初に3 5 421の順序であった場合

解決策は

a。最初に2番目の本のペアを交換します：{結果：3 4 5 2 1}

b。右端のペアを交換します：{結果：3 4 5 1 2}

したがって、2つの動きで、最良の配置を実現します。

私は試しましたが、これに対する解決策を見つけることができませんでした。最初に、配列を2つの配列に分割し、次に両方の配列に挿入ソートを適用しますが、それも機能しません。この質問のアルゴを見つけるのを手伝ってください。

4

1 に答える 1

1

N,1 は、シーケンス内のどこにでも置くことができます。たとえば、1..5 は、3、4、5、1、2 の可能性があります。したがって、最初の桁は 1..5 になる可能性があります。つまり、前の質問の 5 倍複雑です。ということで、5回やる必要があります。置換可能な比較機能を持つソート アルゴリズムを使用します。

したがって、3 番目のテストでは、比較は次のようになります。

// returns <0, 0 or >0
int compare(a,b){
     return ((b+N-3)%N) - ((a+N-3)%N);
}
于 2013-03-13T18:11:17.937 に答える