30pts,除了1,2,3全TLE了,求助
查看原帖
30pts,除了1,2,3全TLE了,求助
789890
pingpig楼主2023/10/16 19:30
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
long long m,n;
long long getg[100005],gra[100005];
long long chk(long long x,long long g)
{
	long long cnt=0;
	for(long long i=0;i<m;i++)
		if(abs(getg[i]-g)<=x)
			cnt++;
	return cnt;
}

int main()
{
	cin>>m>>n;
	for(long long i=0;i<m;i++)
		cin>>getg[i];
	for(long long i=0;i<n;i++)
		cin>>gra[i];
	sort(getg,getg+m);
	sort(gra,gra+n);
	long long  ans=0;
	for(long long i=0;i<n;i++)
	{
		long long l=0,r=max(abs(gra[n-1]-getg[0]),abs(gra[0]-getg[m-1])),mid;
		while(l<r)
		{
			mid=(l+r)/2;
			if(chk(mid,gra[i])>=1)
				r=mid;
			else if(chk(mid,gra[i])<1)
				l=mid+1;
		}
		ans+=r;
	}
	cout<<ans<<endl; 
	return 0;
}

想用二分答案做,但是TLE了,求大佬救救,非常感谢!(如有发现什么弱智错误求轻喷)

2023/10/16 19:30
加载中...