Day2-T5 提高1班1最小点对人类智慧题解

常规
1

正如标题所述，最小点对的题是可以发扬人类智慧的：

我们充分发扬人类智慧，以所有点距原点的距离排序，然后取排序后数组元素前后10个与该元素进行计算。

根据我们的直觉，标准答案中的两个点在数组中应该不会离得太远

这样做快得飞起，n<=10^6时都能卡过

很显然，本题连最基本的人类智慧都没有卡掉，真的是太逊了！

求赞

//排序
	for(int i=0;i<n;i++){
		for(int j=i-88;j<=i+88 && j<n;j++){
			if(j<0 || i==j){
				continue;
			}
			if(ans==-1){
				ans=d(a[i],a[j]);
			}else{
				ans=min(ans,d(a[i],a[j]));
			}
		}
	}
3 个赞
2

求点击

2 个赞
3

补楼：


		for(int j=i+1;j<=i+4 && j<n;j++){
			if(ans==-1){
				ans=d(a[i],a[j]);
			}else{
				ans=min(ans,d(a[i],a[j]));
			}
		}

甚至可以这样过，取每个数及其往后四个数，跑得飞快，十个数据点201ms

2 个赞