# 题目

Problem 593. Fleeting Medians

We define two sequences $S=\{S(1),S(2),\dots,S(n)\}$ and $S_2=\{S_2(1),S_2(2),\dots,S_2(n)\}$:

$S(k)=(p_k)^k\mod10007$ where pk is the kth prime number.

$S_2(k)=S(k)+S\left(\left\lfloor\tfrac{k}{10000}\right\rfloor+1\right)$ where $\lfloor\cdot\rfloor$ 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 $F(n,k)=\sum_{i=1}^{n-k+1}M(i,i+k-1)$. 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


# 评论

Fleeting Medians

c#的3元操作符? :还能((i < k2) ? a : b)[t[i]]++;这么用，也是神了
C 和 C++ 的也能够这么用。 –  黄志斌 03-07 08:00

a[i] 也可以写成 i[a] –  黄志斌 03-07 08:03
a[i] 实际上是 *(a+i)，由于加法满足交换律，所以可以对调 a 和 i –  黄志斌 03-07 08:08

c#的bool是bit还是char? –  lt 03-07 08:18
C# 的 bool 占用 1 个字节，char 占用 2 个字节 –  黄志斌 03-07 08:23
sizeof(bool) == 1 –  黄志斌 03-07 08:23
sizeof(byte) == 1 –  黄志斌 03-07 08:23
sizeof(char) == 2 –  黄志斌 03-07 08:23

51: 2
166: 1
167: 3
265: 1
...
3117: 1
3425: 1
3687: 1
4843: 2
4935: 2

0: 3,5621
1: 3,3080
2: 1,1698
3: 5,649
4: 2,578
5: 947
6: 300
7: 61
8: 54
9: 9
10: 1
11: 2

0: 8,862,064
1: 1,037,558
2: 378
k越大，滑动中位数越接近 –  lt 03-07 07:59