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)],呜呜呜