# 题目

Problem 593. Fleeting Medians

We define two sequences and :

where pk is the kth prime number.

where denotes the floor function.

Then let M(i,j) be the median of elements S2(i) through S2(j), inclusive. For example, M(1,10) = 2021.5 and M(102,103) = 4715.0.

Let . For example, F(100,10) = 463628.5 and F(105,104) = 675348207.5.

Find F(107,105). If the sum is not an integer, use .5 to denote a half. Otherwise, use .0 instead.

# 解答

`````` 1: using System;
2: using Skyiv.Utils;
3:
4: static class E593
5: {
6:   static int[] GetS2(int n, int m)
7:   { // nthPrime < n ln(n ln n) for n > 5
8:     var primes = Primes.GetPrimes(0, (int)(n*Math.Log(n*Math.Log(n))));
9:     int[] s1 = new int[n], s2 = new int[n];
10:     for (var i = 0; i < n; i++) {
11:       s1[i] = primes[i].ModPow(i+1, m);
12:       s2[i] = s1[i] + s1[(i+1) / 10000];
13:     }
14:     return s2;
15:   }
16:
17:   static void Main()
18:   { // k must be even
19:     int m = 10007, n = (int)1e7, k = (int)1e5;
20:     Console.WriteLine("n = {0}, k = {1}", n, k);
21:     var s2 = GetS2(n, m);
22:     Console.WriteLine("s2: {0}", s2.Length);
23:     int[] a = new int[m+m-1], b = new int[m+m-1];
24:     var t = new int[k]; Array.Copy(s2, t, k); Array.Sort(t);
25:     int k2 = k / 2, c = t[k2 - 1], d = t[k2];
26:     for (var i = 0; i < k; i++) ((i < k2) ? a : b)[t[i]]++;
27:     var z = (c + d) / 2.0;
28:     for (int p, q, i = k; i < n; i++, z += (c + d) / 2.0)
29:       if ((p = s2[i - k]) <= c) {
30:         a[p]--;
31:         if ((q = s2[i]) <= c) { a[q]++; while (a[c] == 0) c--; }
32:         else if (q <= d) a[c = q]++;
33:         else { a[c = d]++; b[d]--; b[q]++; while (b[d] == 0) d++; }
34:       } else { // p >= d
35:         b[p]--;
36:         if ((q = s2[i]) >= d) { b[q]++; while (b[d] == 0) d++; }
37:         else if (q >= c) b[d = q]++;
38:         else { b[d = c]++; a[c]--; a[q]++; while (a[c] == 0) c--; }
39:       }
40:     Console.WriteLine("F(n, k) = {0:F1}", z);
41:   }
42: }
``````

• 第 6 行至第 15 行的 GetS2 方法生成 S2 序列。
• 第 7 行的估计第 n 个素数的不等式请参阅参考资料[2]。
• 第 8 行的 GetPrimes 方法请参阅参考资料[3]。
• 第 11 行的 ModPow 方法请参阅参考资料[4]。
• 第 19 行的 k 必须是偶数，这样，中位数是两个整数的算术平均值。
• 第 23 行的数组 a 和 b 分别保存低于和高于中位数的部分。
• 第 24 行的数组 t 保存的 S2 序列的前 k 个元素，然后排序。
• 第 25 行的整数 c 和 d 是最靠近中间的元素，中位数就是它们的算术平均值。
• 第 26 行初始化数组 a 和 b，下标是序列 S2 的元素值，数组的值是该元素出现的次数。
• 第 27 行的浮点数 z 用于累加中位数，初始化为第 1 个中位数的值。
• 第 28 行开始的主循环使用滑动窗口法求中位数的值。
• 整数 p = s2[i - k] 是滑动时丢弃的值。
• 整数 q = s2[i] 是滑动时增加的值。
• 第 29 行至第 33 行处理 p 位于低半部时的情况。
• 第 34 行至第 38 行处理 p 位于高半部时的情况。

``````\$ mcs 593.cs Primes.cs ModPow.cs && mono 593.exe | gnomon -i
9.2630s | n = 10000000, k = 100000
0.1973s | s2: 10000000
0.0158s | F(n, k) = 96?32?20?42.0
|
Total | 9.4765s
``````