HLlll @ 2022-01-29 02:49:50
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
long long a[5000010];
inline int read()
{ //快速读入
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return x * f;
}
void qsort(int begin, int end, int k)
{
int left = begin;
int right = end;
int mid = a[(begin + end) / 2];
if (begin >= end)
return;
while (left < right)
{
while (a[right] >= mid && left < right)
right--;
while (a[left] <= mid && left < right)
left++;
swap(a[left], a[right]);
}
a[left] = mid;
if (k - 1 < left)
qsort(begin, left - 1, k);
else if (k - 1 > left)
qsort(left + 1, end, k);
else
return;
}
int main()
{
int n, k;
//cin>>n>>k;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
qsort(0, n - 1, k);
printf("%d", a[k]);
return 0;
}
第33行和34行,如果没有等号就只能过后面三个测试(前两个TLE),如果有等号就只能过前面两个测试(后面三个WA),这是为什么啊,求大佬解答
by strcmp @ 2022-01-29 09:55:41
@HLlll
1.一般两种方法:小根堆O
2.这道题是在于练习分治算法,任何排序都是投机取巧的,你真想A这道题就用基数排序。但不建议,最好去学一下正解。
分治和小根堆请自己去BDFS。
by strcmp @ 2022-01-29 09:57:17
@wql463 小根堆容易被卡成
by yeanna @ 2022-08-10 18:39:07
@wql463 请问怎么看出来的10^8很悬,怎么看出来的是0(n)的题
by LCATreap @ 2022-08-10 22:22:21
@yeanna 一般默认评测姬速度是每秒
一般用数据范围判断时间复杂度
by yeanna @ 2022-08-11 10:50:43
@wqlGZZC 感谢!