w_god @ 2023-08-31 11:46:47
#include<bits/stdc++.h>
using namespace std;
int a[5000010];
void quick_sort(int q[], int l, int r)
{
if (l >= r) return; // 已经排好序了，直接返回
int i = l - 1, j = r + 1;
int mid = q[l + r >> 1]; // mid 为分界点
while (i < j)
{
do i ++ ; while (q[i] < mid);
do j -- ; while (q[j] > mid);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r); // 递归左右两边
return;
}
int main(void)
{
int n , k;
scanf("%d%d" , &n , &k);
for (int i = 1 ; i <= n ; i++)
{
scanf("%d" , &a[i]);
}
quick_sort(a , 1 , n);
printf("%d" , a[k + 1]);
}by walnut_hubby @ 2023-08-31 11:57:29
你谷评测鸡危
by jqQt0220 @ 2023-08-31 12:29:08
最后递归两边加这样优化：
if(k<=j)quick_sort(q,l,j);
else if(i<=k)quick_sort(q,i,r);
else printf("%d",q[j+1]);还有最好数组从 0 开始好处理
by xiaoshumiao @ 2023-08-31 12:34:41
@w_god 这道题需要用O(n)算法才能过。正解是使用快速排序思想。
by w_god @ 2023-08-31 12:40:31
@xiaoshumiao 可是我这个就是快速排序啊awa（难道是我学错了嘛
by rnf5114 @ 2023-08-31 12:42:14
@w_god 这种事情很正常
by rnf5114 @ 2023-08-31 12:42:27
正解被卡了的概率也不是没有
by rnf5114 @ 2023-08-31 12:42:55
真到考场了也是会开O2的
by xiaoshumiao @ 2023-08-31 12:45:04
@w_god 快速排序时间复杂度为O(nlogn)，过不了。可以去看题解学习一下做法。这道题不是直接的快速排序，而使用它的思想。
by w_god @ 2023-08-31 12:46:47
@xiaoshumiao OK，蟹蟹大佬指点
by Martin_L @ 2023-09-15 22:09:58
还真是！受不了啦
没开O2优化最后一个点TLE，开了真就过啦？
真是……
泰裤辣！！！