社区讨论

大佬帮忙看看为什么不行

P1923【深基9.例4】求第 k 小的数参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@m1ax96e3
此快照首次捕获于
2024/09/21 00:15
去年
此快照最后确认于
2025/11/04 20:47
4 个月前
查看原帖
C
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int n, k;
int a[5000001], b[5000001], c[5000001], d[5000001];
void px(int s, int l)
{
	if (s >= l)
	{
		return;
	}
	int mid = rand() % (l - s) + s;
	int tb = 0, tc = 0, td = 0;
	for (int i = s; i < l; i++)
	{
		if (a[i] < a[mid])
		{
			b[++tb] = a[i];
		}
		else if (a[i] > a[mid])
		{
			c[++tc] = a[i];
		}
		else
		{
			d[++td] = a[i];
		}
	}
	for (int i = 1; i <= tb; i++)
	{
		a[s + i - 1] = b[i];
	}
	for (int i = 1; i <= td; i++)
	{
		a[s + tb + i - 1] = d[i];
	}
	for (int i = 1; i <= tc; i++)
	{
		a[s + tb +td + i - 1] = c[i];
	}
	px(s, tb+s);
	px(tb + td + s, l);
}
int main()
{
	srand((unsigned int)time(0));
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
	px(0, n);
	printf("%d", a[k]);
	return;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...