-3

http://www.codechef.com/problems/LEBOBBLE

n 個の整数の任意の配列 A に対するバブル ソートは、次のように機能します。

var int i, j; 
for i from n downto 1 
{ 
  for j from 1 to i-1 
  { 
    if (A[j] > A[j+1]) 
    swap(A[j], A[j+1]) 
  } 
}

n 個の整数の配列 B が与えられます。

次に、次のように配列 B を使用して配列 A が作成されます。各 i (1 <= i <= n) について、確率 Pi で Ai = Bi + d を設定し、それ以外の場合は Ai = Bi を設定します。配列 A が上記のバブル ソート アルゴリズムでソートされたときに、バブル ソートが行うスワップの期待数を知るために、リトル エレファントを助けてください。入力

入力の最初の行には、単一の整数 T (テスト ケースの数) が含まれます。T テスト ケースは次のとおりです。各テスト ケースの最初の行には、整数 n と d のペアが含まれます。各テスト ケースの次の行には n 個の整数 (配列 B) が含まれます。次の行には n 個の整数 (配列 P) が含まれます。すべての数値は小数点以下 4 桁に丸めてください。制約

1 <= T <= 5
1 <= n <= 50000
1 <= Bi, d <= 10^9
0 <= Pi, <= 100
Example

Input:
2
2 7
4 7
50 50
4 7
5 6 1 7
25 74 47 99

Output:
0.2500
1.6049

これにアプローチする方法についてのヒントはありますか？

4

1 に答える 1

2

ヒントとして、バブル ソートで行われるスワップの数は、配列内の反転の数と同じです。時間 O(n log n) で配列内の反転の数を計算する有名な分割統治アルゴリズムがあります-これを行う方法を理解できますか?

お役に立てれば！

于 2013-06-12T19:14:56.810 に答える