qwq2519 @ 2021-06-18 23:51:05
#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i(j);i <=k ; ++i)
#define drp(i,j,k) for(register int i(j);i >=k ; --i)
using namespace std;
inline char gt()
{
static char buf[1 << 21], *p1 = buf , *p2 = buf;
return p1 == p2 && ( p2 = ( p1 = buf ) + fread( buf , 1 , 1 << 21, stdin ), p1 == p2);
}
template < typename T >
inline void read( T &x )
{
x = 0;
register char ch = getchar();
int w = 0;
while(!(ch >= '0' && ch <= '9')) w |= ch == '-', ch = getchar();
while(ch >= '0' && ch <= '9') x = x * 10 + (ch & 15), ch = getchar();
w ? x = ~(x - 1) : x;
}
template<typename T>
inline void out(T x)
{
if(x < 0) putchar('-'), x = -x;
char s[20];
int num(0);
while(!num || x) s[++num] = x % 10 + '0', x /= 10;
while(num) putchar(s[num--]);
putchar(' ');
}
const int MAX = 1e6 + 79;
int N, k;
int a[MAX];
void Quick_Sort(int *q, int l, int r, int t)
{
int cnt = 0;
if(l >= r) {
cout << q[l] << ' ';
return ;
}
int i = l - 1, j = r + 1, x = q[(l + r) >> 1];
while(i < j) {
while(q[++i] < x) cnt++;
while(q[--j] > x);
if(i < j) swap(q[i], q[j]);
}
if(cnt == t) {
cout<<x<<' ';
return;
}
if(cnt > t)Quick_Sort(q, l, j, t);
else Quick_Sort(q, j + 1, r, t - cnt);
}
int main()
{
cin >> N >> k;
// read(N);read(k);
rep(i, 1, N)cin >> a[i];
// read(a[i]);
Quick_Sort(a, 1, N, k + 1);
return 0;
}
我的快排可能比较奇怪。。。不是边递归边计数吗,不断二分找到目标区间。。不知道哪里错了,思路是对的。。但是细节不知道哪里错了