Yin_haoran233 @ 2022-01-06 01:48:42
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
const int N = 1e6 + 10;
int m[N], n[N], x, y, sum = 0;
void quiklysort(int arr[], int left, int right) {
if (left >= right)return;
int pivot = arr[(left + right) / 2];
int L = left - 1;
int R = right + 1;
while (L < R) {
do {
L++;
} while (arr[L] < pivot);
do {
R--;
} while (arr[R] > pivot);
if (L < R) {
int a = arr[L];
arr[L] = arr[R];
arr[R] = a;
}
}
quiklysort(arr, left, R);
quiklysort(arr, R + 1, right);
}
void seck(int i) {
int tou = 0;
int wei = x - 1;
while ( tou<wei) {
int zhong = (tou + wei) / 2;
if(i==m[zhong]){
return;
}else if(i<m[zhong]){
wei=zhong;//就是这里我不太理解
}else if(i>m[zhong]){
tou=zhong+1;
}
}
if(i<=m[0]){
sum += m[tou] - i;
}else{
if (abs(i - m[tou-1]) > abs(i - m[tou]))sum += abs(i - m[tou]);
else
sum += abs(i - m[tou-1]);
}
}
int main () {
scanf("%d %d", &x, &y);
for (int i = 0; i < x; i++)scanf("%d", &m[i]);
quiklysort(m, 0, x - 1);
for (int i = 0; i < y; i++)scanf("%d", &n[i]);
for (int i = 0; i < y; i++)seck(n[i]);
printf("%d", sum);
return 0;
}```
就是再二分查找时候,出现要查找的值小于中间值时,直接将中间端点序号赋给右端点,但是当查找值大于中间值时候,左端点序号是中间端点序号加一,我一直不太理解这个事情,求大佬们解答,对应代码位置我已经标注出来了。
by xwh_Marvelous @ 2022-01-06 11:09:00
二分查找有不止一种写法。我是 l=mid+1
r=mid-1
这样查找的。你这样应该也行
by Arkeris @ 2022-01-20 18:37:48
这里赋值给tou的值可以是zhong,zhong+1,赋值给wei的值可以是zhong,zhong-1,+1和-1是为了减少运行时间,减少重复查找。其实也没多大用,也可以不写,你那样也是一种方法。