三、阅读程序-2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

/**************************************************************** 
 * Description: 2022_CSP_S_2
 * Author: Alex Li
 * Date: 2023-08-18 05:15:45
 * LastEditTime: 2023-08-18 06:04:49
****************************************************************/
#include <iostream>
using namespace std;
  
  const int MAXN = 105;
  
  int n, m, k, val[MAXN];
  int temp[MAXN], cnt[MAXN];
  
 void init() 
 {
     cin >> n >> k;
     for (int i = 0; i < n; i++) cin >> val[i];
     int maximum = val[0];
     for (int i = 1; i < n; i++)
         if (val[i] > maximum) maximum = val[i];
     m = 1;
     while (maximum >= k) {
         maximum /= k;
         m++;
     }
 }
 
 void solve() 
 {
     int base = 1;
     for (int i = 0; i < m; i++) {
         for (int j = 0; j < k; j++) cnt[j] = 0;
         for (int j = 0; j < n; j++) cnt[val[j] / base % k]++;
         for (int j = 1; j < k; j++) cnt[j] += cnt[j - 1];
         for (int j = n - 1; j >= 0; j--) {
             temp[cnt[val[j] / base % k] - 1] = val[j];
             cnt[val[j] / base % k]--;
         }
         for (int j = 0; j < n; j++) val[j] = temp[j];
         base *= k;
     }
 }
 
 int main() 
 {
     init();
     solve();
     for (int i = 0; i < n; i++) cout << val[i] <<' ' ;
     cout << endl;
     return 0;
 }