-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)，我们设置 Ai = Bi + d 的概率为 Pi，否则 Ai = Bi。帮助 Little Elephant 找出当使用上述冒泡排序算法对数组 A 进行排序时冒泡排序将进行的预期交换次数。输入

输入的第一行包含单个整数 T - 测试用例的数量。T 测试用例如下。每个测试用例的第一行包含一对整数 n 和 d。每个测试用例的下一行包含 n 个整数 - 数组 B。下一行包含 n 个整数 - 数组 P。输出 T 行输出 T 个实数 - 对应测试用例的答案。请将所有数字四舍五入到小数点后 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 回答