组合题6 个小题
已作答 0 / 6
11 #include <iostream>2233 using namespace std;4455 const int MAXN = 105;6677 int n, m, k, val[MAXN];88 int temp[MAXN], cnt[MAXN];991010 void init()1111 {1212 cin >> n >> k;1313 for (int i = 0; i < n; i++) cin >> val[i];1414 int maximum = val[0];1515 for (int i = 1; i < n; i++)1616 if (val[i] > maximum) maximum = val[i];1717 m = 1;1818 while (maximum >= k) {1919 maximum /= k;2020 m++;2121 }2222 }23232424 void solve()2525 {2626 int base = 1;2727 for (int i = 0; i < m; i++) {2828 for (int j = 0; j < k; j++) cnt[j] = 0;2929 for (int j = 0; j < n; j++) cnt[val[j] / base % k]++;3030 for (int j = 1; j < k; j++) cnt[j] += cnt[j - 1];3131 for (int j = n - 1; j >= 0; j--) {3232 temp[cnt[val[j] / base % k] - 1] = val[j];3333 cnt[val[j] / base % k]--;3434 }3535 for (int j = 0; j < n; j++) val[j] = temp[j];3636 base *= k;3737 }3838 }39394040 int main()4141 {4242 init();4343 solve();4444 for (int i = 0; i < n; i++) cout << val[i] << ;4545 cout << endl;4646 return 0;4747 }假设输入的 n 为不大于 100 的正整数,k 为不小于 2 且不大于 100 的正整数,val[i]在 int 表示范围内,完成下面的判断题和单选题:
判断题
该算法的时间复杂度为O(m(n+k))。( ) 单选题