cloudemakers @ 2022-12-10 13:21:26
#include<bits/stdc++.h>
using namespace std;
int a[6000000];
int n,k;
int qs(int l,int r){
if (l==r) return a[l];
int ll=l,rr=r,mid=(l+r)/2;
while (ll<=rr){
while (a[ll]<a[mid]) ll++;
while (a[rr]>a[mid]) rr--;
if (ll<=rr){
swap(a[ll],a[rr]);
ll++,rr--;
}
}
if (k<=rr) qs(l,rr);
else if (ll<=k) qs(ll,r);
else qs(rr+1,ll-1);
}
int main(){
scanf("%d%d",&n,&k);
for (int i=0;i<n;i++) scanf("%d",&a[i]);
printf("%d",qs(0,n-1));
return 0;
}
rt,这个代码0分 而把mid改成a[(l+r)/2],再把下面的a[mid]直接换成mid后就可以通过 这是怎么回事?
by yukimianyan @ 2022-12-10 13:53:13
因为
by cloudemakers @ 2022-12-11 13:17:17
@yukimianyan emmm 具体是为什么呢?
by 渣渣炜 @ 2022-12-17 19:31:54
@cloudemakers 每一轮是保证左边的小于等于稍兵的值,右边的大于等于稍兵的值。你开始写下标的话,稍兵可能被丢到后面去,这样后面的比较就找不到“稍兵的值”了,你的mid是其他的了