本题是一道考察计数排序的简单题，如果你不了解计数排序，可以来看看！
作者：余绍函
题目描述
对于一个数组 ，定义 其中
现给出一个随机数生成器如下：
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
| #include <stdio.h>
#define N 5000005
int nextRand() {
static unsigned int rnd_num = 0x80000001;
static int mod = 1e5 + 3;
rnd_num ^= rnd_num >> 10;
rnd_num ^= rnd_num << 9;
rnd_num ^= rnd_num >> 25;
return rnd_num % mod;
}
int a[N];
int main() {
int tt;
scanf("%d", &tt);
while (tt--) {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
a[i] = nextRand();
}
}
return 0;
}
|
对于每组测试数据，你需要使用上述随机数生成器生成 个数 记 ，你需要求出 的值。
注意：对于一个测试点有多组测试数据，在每组测试数据之间不需要重置随机数生成器，在后一组测试中，只需要继续调用随机数生成器直接得到随机数即可。
输入
第一行一个正整数 (1≤ ≤ 10) 表示数据组数。
接下来组数据：
一行一个正整数 A的长度。
输出
对于每组数据，输出一行一个正整数表示的值。
输入样例
输出样例
1
2
3
| 3832359
353053098
34254309646
|
提示
一个数 的 定义为 数组内全部元素 比它小的数的个数加一，例如对于 有：
因此
另外，提醒大家多多注意代码中 的范围。
解题思路
因为这道题需要求 ，所以这道题需要给生成的随机数进行排序。由于时间限制比较严格，同时数据组数多、数据量大，如果使用qsort或者其余时间复杂度为 的排序函数很容易TLE。不难发现，生成随机数的范围是 ，范围比较小。因此我们可以采用的计数排序法。
计数排序
计数排序假设n个输入元素中的每一个都是在0到k的一个整数。当 时，排序的运行时间为 。
计数排序的基本思想是:对每一个输入元素，确定小于的元素个数。利用这一信息，就可以直接把放到它在输出数组中的位置上了。例如，如果有 个元素小于 ，则 就应该在第18个输出位置上。当有几个元素相同时，这一方案要略做修改。因为不能把它们放在同一个输出位置上。
伪代码：
代码实现
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
| #include <stdio.h>
#define N 5000005
int nextRand() {
static unsigned int rnd_num = 0x80000001;
static int mod = 1e5 + 3;
rnd_num ^= rnd_num >> 10;
rnd_num ^= rnd_num << 9;
rnd_num ^= rnd_num >> 25;
return rnd_num % mod;
}
int array[N], barrel[100010], last_count;
long long f;
int main() {
int tt;
scanf("%d", &tt);
while (tt--) {
int n;
scanf("%d", &n);
for(int i = 0; i <= 100003; i++)
barrel[i] = 0;
for (int i = 1; i <= n; i++) {
array[i] = nextRand();
barrel[array[i]]++;
}
f = last_count = 0;
for(int i = 0; i <= 100003; i++)
{
if(barrel[i] > 0)
{
f += (long long)barrel[i] * (long long)(last_count + 1) * (long long)i;
last_count += barrel[i];
}
}
printf("%lld\n", f);
}
return 0;
}
|
思考与拓展
计数排序的使用条件
- 给整数排序
- 需要排序的数据范围较小
- 拥有充足的空间（空间复杂度与需要排序的数据范围相关）
带有负数时计数排序的使用
假设需要排序的数组是，的范围是 $l,rcountr-l+1$ ，在计数时执行count[A[index] - l]++，在遍历计数数组取count[i]+l，其中 。
一些可以使用计数排序的题目
leetcode 83
leetcode 147
leetcode 148