求解距离多个点距离之和最小的点,给出这个点的坐标,给出最小的距离

package bushi;
import java.util.Scanner;
public class zuijng {

        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            System.out.print("请输入点的个数:");
            int n = scanner.nextInt();
            int[][] points = new int[n][2];
            System.out.println("请输入" + n + "个点的坐标(x, y):");
            for (int i = 0; i < n; i++) {
                System.out.print("第" + (i+1) + "个点:");
                points[i][0] = scanner.nextInt();
                points[i][1] = scanner.nextInt();
            }

            int x = points[0][0];
            int y = points[0][1];
            int sum = 0;
            for (int i = 1; i < n; i++) {
                sum += getDistance(x, y, points[i][0], points[i][1]);
            }

            for (int i = 1; i <= 100; i++) { // 枚举平面上的点,找到距离之和最小的点
                for (int j = 1; j <= 100; j++) {
                    int tempSum = 0;
                    for (int k = 0; k < n; k++) {
                        tempSum += getDistance(i, j, points[k][0], points[k][1]);
                    }
                    if (tempSum < sum) {
                        sum = tempSum;
                        x = i;
                        y = j;
                    }
                }
            }

            System.out.println("在该平面上," + n + "个点中到一个点(" + x + ", " + y + ")的距离之和最小,为" + sum);
        }

        public static int getDistance(int x1, int y1, int x2, int y2) {
            return Math.abs(x1 - x2) + Math.abs(y1 - y2);
        }
    


    }

运行报错

  • 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7541092
  • 你也可以参考下这篇文章:统计逆序对的个数,并输出具体的逆序对(分治算法)
  • 除此之外, 这篇博客: 输入一个数,找出小于这个数的所有质数中的 找出小于输入数的所有质数 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  • 代码实现如下:

    # include<iostream>
    using namespace std;
    
    int main() {
    	//被除数
    	int i;
    	//除数
    	int j;
    	//遍历数组时的索引
    	int i1;
    	int i2;
    	cout<<"请输入一个int型的数"<<endl;
    	cin>>i;
    	//声明一个数组,用来放入找到的质数
    	int arr[1000] = {0};
    	//存入元素的时候的下标
    	int n = 0;
    	//循环拿出被除数
    	for (i ; i > 1 ; i--) { 
    		j = i -1;
    		//循环拿出除数
    		for(j ; j > 1 ; j--) {
    			//拿被除数i除以除数j余数是0,则这个被除数i不是质数,直接退出循环
    			if (i % j == 0) {
    				break;
    			}
    		}
    		//当除数j变为1时,说明i为质数
    		if(j == 1) {
    			//将质数存入数组
    			arr[n] = i;
    			n++;
    		}
    	}
    
    	for (i1 = 0 ; i1 < sizeof(arr)/sizeof(int) ; i1++) {
    		if(arr[i1] != 0) {
    			cout<<arr[i1]<<" ";
    		}
    	}
    	cout<<endl;
    	return 0;
    }
    
  • 您还可以看一下 孙玖祥老师的图解数据结构与算法课程中的 左旋和右旋的代码实现小节, 巩固相关知识点