论mid的下标和值的关系

P1923 【深基9.例4】求第 k 小的数

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

因为 a_{mid} 这个值会变


by cloudemakers @ 2022-12-11 13:17:17

@yukimianyan emmm 具体是为什么呢?


by 渣渣炜 @ 2022-12-17 19:31:54

@cloudemakers 每一轮是保证左边的小于等于稍兵的值,右边的大于等于稍兵的值。你开始写下标的话,稍兵可能被丢到后面去,这样后面的比较就找不到“稍兵的值”了,你的mid是其他的了


|