#3 #9wa,不直到错哪里了,求调,谢谢大佬们
查看原帖
#3 #9wa,不直到错哪里了,求调,谢谢大佬们
1066414
lwj1239楼主2023/12/29 07:31
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 100000

int a[N];
int b[N];

typedef int ELEMENT;

void quickSort(ELEMENT *a, int low, int high);
void swap(ELEMENT *a, int low, int high);//½»»»a[low]ºÍa[high]µÄÖµ 
int* partition(ELEMENT *a, int low, int high, ELEMENT key);//°ÑaÖÐlowµ½highµÄÊý°´ÕÕkey·ÖÀ࣬СÓÚkeyµÄÔÚ×ó±ß£¬µÈÓÚkeyµÄÔÚÖм䣬´óÓÚkeyµÄÔÚÓÒ±ß
int min(int a, int b)
{
	return a >= b? b: a;
}

int main(int argc, char* argv[])
{
	int m, n;
	
	scanf("%d%d", &m, &n);
	
	
	
	for (int i = 0; i < m; i++) {
		scanf("%d", a + i);
	}
	
	for (int j = 0; j < n; j++) {
		scanf("%d", b + j);
	}
	
	quickSort(a, 0, m - 1);
	
	ll minsum = 0;
	
	for (int j = 0; j < n; j++) {
		int l = 0;
		int r = m - 1;
		int ans = -1;
		
		while(l <= r) {
			int mid = (l + r) / 2;
			
			if (a[mid] >= b[j]) {
				ans = mid;
				r = mid - 1;
			}
			else {
				l = mid + 1;
			}
		}
		
		if (ans == 0) {
			minsum += abs(a[ans] - b[j]);
		}
		else {
			minsum += min(abs(a[ans] - b[j]), abs(a[ans - 1] - b[j]));
		}
	}
	
	printf("%lld", minsum);
	
	return 0;
}

void quickSort(ELEMENT *a, int low, int high)
{
	int *p = NULL;//´æ´¢µÈÓÚ»ù×¼ÖµµÄ×óÓұ߽ç 
	
	if ( low >= high) {//Èç¹ûÖ»ÓÐÒ»¸öÖµ²»ÓÃÅÅÐò¾ÍÖ±½Ó½áÊøÅÅÐò 
		return ;
	}
	
	p = partition(a, low, high, a[low + rand() % (high - low + 1)]);//pÖ¸ÏòµÈÓÚ»ù×¼ÖµÇø¼ä×óÓұ߽ç 
	quickSort(a, low, p[0] - 1);//Ö»ÅÅСÓÚ»ù×¼ÖµµÄ²¿·Ö 
	quickSort(a, p[1] + 1, high);//Ö»ÅÅ´óÓÚ»ù×¼ÖµµÄ²¿·Ö
	free(p);//Êͷŵô¿ª±ÙµÄ¿Õ¼ä 
}
void swap(ELEMENT *a, int low, int high)
{
	ELEMENT t = 0;
	
	t = a[low];
	a[low] = a[high];
	a[high] = t;
}
int* partition(ELEMENT *a, int low, int high, ELEMENT key)
{
	int l = low;//´ú±íµÈÓÚkeyÇø¼äµÄ×ó±ß½ç,»òÕßÊÇСÓÚÇø¼äµÄÏÂÒ»¸öÊý  
	int r = high;//´ú±íµÈÓÚkeyÇø¼äµÄÓұ߽ç,»òÕßÊÇ´óÓÚÇø¼äµÄÏÂÒ»¸öÊý  
	int i = low;//´ÓÍ·¿ªÊ¼±éÀú 
	
	while(i <= r) {//ֻҪûÓе½´óÓÚÇø¼ä 
		if (a[i] < key) {//ϱêiµÄÊýСÓÚ»ù×¼Öµ£¬·ÅÔÚ×ó±ß½çÀïÃæ 
			swap(a, l++, i++);//°Ñ×ó±ß½çµÄºóÒ»¸öÊýºÍϱêiµÄÖµ½»»»£¬È»ºó×óÇø¼äÀ©ÕÅ£¬È»ºóÈ¥¿´ÏÂÒ»¸öÊý 
		}
		else  if ( a[i] > key){//ϱêiµÄÊý´óÓÚ»ù×¼Öµ£¬·ÅÔÚÓұ߽çÀïÃæ 
			swap(a, r--, i);//°ÑÓұ߽çµÄǰһ¸öÊýºÍϱêiµÄÖµ×ö½»»»£¬È»ºóÓÒÇø¼äÀ©ÕÅ£¬µ«i²»Äܶ¯£¬ÒòΪµ±Ç°iµÄÖµ»¹Ã»ÓзÃÎʹý 
		}
		else {//ϱêiµÄÊýµÈÓÚ»ù×¼Öµ£¬·ÅÔÚ×óÓұ߽çÖ®¼ä 
			i++;//Ö±½Ó¼Ó1
		}
	} 
	int *p = (int *)malloc(sizeof(int ) * 2);//´æ·ÅµÈÓÚÇø¼äµÄ×óÓұ߽ç 
	p[0] = l;//µÈÓÚÇø¼ä×ó±ß½ç¾ÍÊÇl
	p[1] = r;//µÈÓÚÇø¼ä×ó±ß½ç¾ÍÊÇr
	return p;//·µ»ØµÈÓÚkeyÇø¼äµÄ×óÓұ߽ç 
}
2023/12/29 07:31
加载中...