问到大佬们一个问题,一直不解。
查看原帖
问到大佬们一个问题,一直不解。
574873
Yin_haoran233楼主2022/1/6 01:48
#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;
}```
就是再二分查找时候,出现要查找的值小于中间值时,直接将中间端点序号赋给右端点,但是当查找值大于中间值时候,左端点序号是中间端点序号加一,我一直不太理解这个事情,求大佬们解答,对应代码位置我已经标注出来了。
2022/1/6 01:48
加载中...