(l + r) >> 1 和l + (r - l) >> 1的问题

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

24222400583Xyy @ 2024-03-13 22:22:05

(l + r) >> 1 和l + (r - l) >> 1的问题 快排思想二分只排序k所在区域,最后输出第k个数,但是!!!: 我的用来比较的数写成这样int x = q[(l + r) >> 1 ]能过,但是写成q[l + (r - l) >> 1]全TLE。为啥啊

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5e6 + 10;
int n, q[N];

void quick_sort(int q[], int l, int r, int k) {
    if(l >= r)return;
    int x = q[l + (r - l) >> 1];
    int i = l - 1, j = r + 1;
    while(i < j) {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) 
            swap(q[i], q[j]);
    }
    if(j >= k)
        quick_sort(q, l, j, k);
    else 
        quick_sort(q, j + 1, r, k);
}
int main() {
    int k;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++) scanf("%d", q + i);
    quick_sort(q, 0, n - 1, k);
    printf("%d", q[k]);
//  for(int i = 0; i < n; i++) printf("%d ", q[i]); 
    return 0;
}

by 24222400583Xyy @ 2024-03-13 22:31:52

我明白了,太粗心大意了,加法优先级比>>高,应该写成q[l+(r-l>>1)],呜呜呜


|