_Hal @ 2023-07-21 12:18:09
#include <iostream>
#include <string>
const int N = 50000010;
int k;
int arr[N];
void swap(int& a, int&b)
{
int temp = a;
a = b;
b = temp;
}
int qu_sort(int arr[], int l, int r, int k)
{
if (l == r)
{
return arr[l];
}
int i = l - 1, j = r + 1, x = arr[l + r >> 1];
while (i < j)
{
do
{
i++;
} while (arr[i] < x);
do
{
j--;
} while (arr[j] > x);
if (i < j)
{
swap(arr[i], arr[j]);
}
}
int len = r - l + 1;
if (k < len)
{
qu_sort(arr, l, j, k);
}
else
{
qu_sort(arr, j + 1, r, k - len);
}
}
int main()
{
int i, n;
scanf("%d %d\n", &n, &k);
for (i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
std::cout << qu_sort(arr, 0, n - 1, k + 1);
system("pause");
return 0;
}
by __Tonycyt__ @ 2023-07-21 13:11:42
蒟蒻谢罪
by Terrible @ 2023-07-21 13:12:35
@ln2____ 具体地说,是依赖于数据随机的期望
推荐使用 std::nth_element
函数,对任何正确的输入参数都能以
by Terrible @ 2023-07-21 13:13:20
@Tonycyt 快去好好学习。
by _Hal @ 2023-07-21 13:20:27
@Terrible 谢谢兄弟!爱死了爱死了!!
by _Hal @ 2023-07-21 13:24:01
@Terrible 大佬为什么要变成<=呢
by Terrible @ 2023-07-21 13:28:37
@ln2____ 你的代码将序列分成了两部分,一部分是
反过来想,如果 k==len
放到右边的部分,会把
by _Hal @ 2023-07-21 13:30:36
@Terrible 嗷嗷我缕一缕
by __Tonycyt__ @ 2023-07-21 14:30:52
@Terrible 请尽量不要使用 nth_element
来写本题,因为本题的重点在于练习分治算法。
by __Tonycyt__ @ 2023-07-21 14:31:51
我会 nth_element
要是没有这句话我早让他用了