sdut oj 4228 第k小的数（数据加强版）

缘起

上次【1】中我们学习了topK问题的各种解法，可就是 sdut 4228 第k小的数（数据加强版) 总是T. 题意见【1】. 于是不甘心的我清晨眼没睁开的时候在脑海里想突破口——想到了~

分析

关键是注意到”所有整数互不相同而且在[1,90000000]这个固定范围内”~ 自然想到桶排序. 但是考虑到内存有限（你开一个bool a[9千万]就要用掉差不多90MB内存，必定MLE），所以使用位图法进行优化（优化到了23+MB）. 这题如果想到了，就是个水题. 没想到，一直T到你死. 剩下的就没什么好说的了~ 上代码

ac代码

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
53
54
#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#define LOCAL
const int maxn = 3000000;
int n,k,a, _max;
unsigned int c[maxn]; // bitmap进行桶排
int s[maxn]; // s[i]表示c的第i个字节出现数字的次数

int main() {

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		_max = 0;
		memset(c, 0, sizeof(c));
		memset(s, 0, sizeof(s));
		scanf("%d%d", &n,&k);
		while(n--)
		{
			scanf("%d", &a);
			c[a>>5] |= (1<<(a%32)); // 要操作的字节位于 a/32, 而记录是从低比特位开始记录的
			s[a>>5]++;
			if (a>_max) _max =  a;
		}
		int i = -1,tmp;
		while(k>0)
		{
			tmp = k;
			i++;
			k-=s[i];
		} // 最后k<=0, 最后是减去s[i]导致的（s[i]是压垮k的最后一根稻草,则要找的数就在c[i]上面）,而tmp 记录了k最后大于0的值
		int j = 0,y;
		while(1)
		{
			if (c[i] & (1<<j))
			{
				tmp--;
				if (!tmp)
				{
					break; // 最后 c[i]的从低到高第j比特位(j>=0)就是第k个数
				}
			}
			j++;
		}
		printf("%d\n",j+(i<<5));
	}
	return 0;
}

ac情况

6497075 yfs 4228 Accepted 2464 ms 23596 KiB g++ 1126 B 2019-08-15 07:06:20

参考

【1】https://yfsyfs.github.io/2019/08/14/topK-%E9%9D%A2%E8%AF%95%E5%BF%85%E9%97%AE-SDUTOJ-4166-4228-%E6%95%B0%E6%8D%AE%E5%8A%A0%E5%BC%BA-%E7%AC%ACk%E5%B0%8F%E7%9A%84%E6%95%B0-%E5%A0%86%E6%8E%92-%E5%BF%AB%E6%8E%92-kth/