2022 年 S 初赛阅读 阅读程序 T2 （应该吧）

1  #include <iostream>
2  
3  using namespace std;
4  
5  const int MAXN = 105;
6  
7  int n, m, k, val[MAXN];
8  int temp[MAXN], cnt[MAXN];
9  
10 void init() 
11 {
12     cin >> n >> k;
13     for (int i = 0; i < n; i++) cin >> val[i];
14     int maximum = val[0];
15     for (int i = 1; i < n; i++)
16         if (val[i] > maximum) maximum = val[i];
17     m = 1;
18     while (maximum >= k) {
19         maximum /= k;
20         m++;
21     }
22 }
23 
24 void solve() 
25 {
26     int base = 1;
27     for (int i = 0; i < m; i++) {
28         for (int j = 0; j < k; j++) cnt[j] = 0;
29         for (int j = 0; j < n; j++) cnt[val[j] / base % k]++;
30         for (int j = 1; j < k; j++) cnt[j] += cnt[j - 1];
31         for (int j = n - 1; j >= 0; j--) {
32             temp[cnt[val[j] / base % k] - 1] = val[j];
33             cnt[val[j] / base % k]--;
34         }
35         for (int j = 0; j < n; j++) val[j] = temp[j];
36         base *= k;
37     }
38 }
39 
40 int main() 
41 {
42     init();
43     solve();
44     for (int i = 0; i < n; i++) cout << val[i] << ;
45     cout << endl;
46     return 0;
47 }

问：Val 最大值为 100 时，k 取多少算法运算次数最少？

选项：2，3，10，不确定。

洛谷答案是 不确定，B站上的讲解是 10