问到大佬们一个问题,一直不解。

P1678 烦恼的高考志愿

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是为了减少运行时间,减少重复查找。其实也没多大用,也可以不写,你那样也是一种方法。


|