80,排序+双指针,没有二分,求大佬看看
查看原帖
80,排序+双指针,没有二分,求大佬看看
626618
Luckz楼主2022/12/11 19:17
#include <iostream>
using namespace std;
#include <cmath>
#include <algorithm> 

int a[100010];//预估分数线 
int b[100010];//预估成绩 

int main()
{
	int m, n;//学校数,学生数
	long long ans = 0; 
	scanf("%d %d", &m, &n); 
	for(int i = 0; i < m; ++i)
	{
		scanf("%d", &a[i]);
	}
	sort(a, a+m);
	for(int i = 0; i < n; ++i)
	{
		scanf("%d", &b[i]);
	}
	sort(b, b+n);
	int r1 = 0;
	int r2 = 0;
	while(b[r2] <= a[0] && r2 != n)
	{
		ans += a[0] - b[r2];
		r2++; 
	}
	while(r2 != n)
	{
		if(r1 == m)
		{
			ans += abs(b[r2] - a[r1]);
			r2++;
		}
		if(b[r2] >= a[r1])
		{
			if(b[r2] <= a[r1 + 1])
			{
				ans += min(b[r2] - a[r1], a[r1 + 1] - b[r2]);
				r2++;
			}
			//不满足上面的情况
			else
			{
				r1++;
			}
		}
		 
		if(b[r2] < a[r1])
		{
			r1++;
		}	
		
	}
	printf("%lld", ans);
	return 0;
} 

采用的排序+双指针的方法,并没有用二分,就3#Wrong Answer.wrong answer On line 1 column 1, read 1, expected 4. 9#Runtime Error. Received signal 11: Segmentation fault with invalid memory reference. 其他都能过,求大佬们路过能出手相助,虽然我知道这个算法挺垃圾的,不如二分...

2022/12/11 19:17
加载中...