题目

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.

分析

我们使用滑动窗口法来求中位数。由于 0 ≤ S2 ≤ 20012,而 k = 105,所以平均每个元素会出现 5 次,相当密集。因此我们使用数组来表示滑动窗口,而不使用 SortedDictionary<int, int>

解答

我们使用以下 C# 程序来解答此题:

 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 位于高半部时的情况。

这个程序的运行时间是 9 秒。实际上,98% 的时间都用于生成 S2 序列,只有 2% 的时间用于计算中位数,如下所示:

$ 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

参考资料

  1. Wikipedia: Median
  2. Wikipedia: Prime-counting function
  3. 图灵社区:编码:使用筛法生成素数
  4. 图灵社区:编码:幂的计算(C#)