堆棋子

//最后的重叠点的横坐标是n个棋子中的横坐标之一，纵坐标是n个棋子中的纵坐标之一，
//因此考虑这n*n种情况。从网上得到证明（我也不是很理解）：这方法称为曼哈顿距离，
//即方法关键在于求和的时候可以把x和分开，独立分析… import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] x = new int[n];
        int[] y = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            y[i] = sc.nextInt();
        }

        //记录输入的点到可能出现的点的距离
        int dis[] = new int[n];

        //最优解
        int result[] = new int[n];
        //初始化
        for(int i = 0 ; i < n ; i++){
            result[i] = Integer.MAX_VALUE;
        }

        //前两个循环表示：最终移动的点会落在已有的横纵坐标的组合上
        for(int i = 0;i < n ; i++){
            for(int j = 0 ; j < n ; j++){

                //对输入的点进行遍历，计算每个输入的点到 x[i]y[j]的距离
                for(int k = 0 ; k < n ; k++){
                    //dis[0] 表示输入的第0个点到x[i]y[j]的步数
                    dis[k] = Math.abs(x[i]-x[k])+Math.abs(y[j]-y[k]);
                }
                //采用快排对dis进行排序
                Arrays.sort(dis);
                int temp=0;
                for(int t = 0 ; t < n ; t++){
                    //累加 t 个点 移动到 x[i]y[j]的步数
                    temp = temp + dis[t];

                    //result[t] 会在每次不同的 x[i]y[j] 时更新最小值
                    result[t] = Math.min(result[t],temp);
                }

            }
        }
        //最后不能有空格
        System.out.print(result[0]);
        for(int i = 1;i<n;i++){
            System.out.print(" "+result[i]);
        }
    }
}

	

import java.util.Arrays;
import java.util.Scanner; 
public class Main { 
     public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] x = new int[n];
        int[] y = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            y[i] = sc.nextInt();
        }
        sc.close();
        int[] dis = new int[n];
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    dis[k] = Math.abs(x[k] - x[i]) + Math.abs(y[k] - y[j]);
                }
                Arrays.sort(dis);
                int temp = 0;
                for (int r = 0; r < n; r++) {
                    temp += dis[r];
                    result[r] = Math.min(temp, result[r]);
                }
            }
        }
        for (int i = 0; i < n - 1; i++) {
            System.out.print(result[i] + " ");
            System.out.println(result[n - 1]);
        }
    }

}

答案中都设计到一个排序，比如Arrays.sort(dis);

排序的目的是计算每个棋子落到指定点位的最小步数（题目要求最少步数）。同时题干还有个要求就是点位的棋子累加的（有一个棋子在格子，有两个棋子在格子），所以必须将求得的结果从小到大排个序

不进行排序求得的结果就不是最小步数

import java.util.Scanner;
import java.util.Arrays;

//假设i个元素所在的点的坐标是（x0,y0），称作目标点
//x0一定属于x[0]...x[n]
//y0一定属于y[0]...y[n]
//设输出是res[n]，res[i]表示 某个点有i+1个元素的最小操作数。
public class Main {
       public static void main(String args[]){
       
        //读输入
        Scanner scanner = new Scanner(System.in);
        String[] input = new String[3];
        int index = 0;
        while (scanner.hasNext()){
            input[index] = scanner.nextLine();
            index++;
            if (index>=3){
                break;
            }
        }
        int n = Integer.valueOf(input[0]);
        String[] strx = input[1].split(" ");
        String[] stry = input[2].split(" ");
        int x[] = new int[n];
        int y[] = new int[n];
        for (int i=0;i<n;i++){
            x[i] = Integer.valueOf(strx[i]);
            y[i] = Integer.valueOf(stry[i]);
        }
        
        //
        int res[] = new int[n];//结果
        int dis[] = new int[n];//一次遍历的结果
        for (int i = 0;i<n;i++){
            res[i] = Integer.MAX_VALUE;
        }
        res[0] = 0;

        //遍历所有目标点的排列组合
        for (int i = 0;i<n;i++){
            for (int j=0;j<n;j++){
                //对目标点（x[i],y[j]）,遍历n个点到目标点的距离
                for (int k=0;k<n;k++){
                    dis[k] = Math.abs(x[k]-x[i])+Math.abs(y[k]-y[j]);
                }
                Arrays.sort(dis);//快排，nlogn
                for (int k=1;k<n;k++){
                    dis[k]= dis[k-1]+dis[k];//（x[i],y[j]) 目标点中有k+1个元素的最小操作数
                    res[k] = Math.min(dis[k],res[k]);//结果取当前值和历史值的较小值
                }
            }
        }

        //打印
        StringBuilder resBulider = new StringBuilder();
        for (int i=0;i<n-1;i++){
            resBulider.append(res[i]+" ");
        }
        resBulider.append(res[n-1]);
        System.out.println(resBulider.toString());
    }
}
 

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        HashSet<Integer> hashSetX=new HashSet<>();
        HashSet<Integer> hashSety=new HashSet<>();
        int n=scan.nextInt();
        int[] x=new int[n];
        int[] y=new int[n];
        StringBuilder ret=new StringBuilder();
        for (int i = 0; i < n; i++) {
            x[i]=scan.nextInt();
            hashSetX.add(x[i]);
        }
        for (int i = 0; i < n; i++) {
            y[i]=scan.nextInt();
            hashSety.add(y[i]);
        }
        int[][] candidateToN=new int[hashSetX.size()*hashSety.size()][n];
        int begin=0;
        for (int i:hashSetX) {
            for (int j:hashSety) {
                for (int k = 0; k < n; k++) {
                    candidateToN[begin][k]=Math.abs(x[k]-i)+Math.abs(y[k]-j);
                }
                begin++;
            }
        }
        for (int i = 0; i < candidateToN.length; i++) {
            Arrays.sort(candidateToN[i]);
        }
        for (int i = 0; i < candidateToN.length; i++) {
            for (int j = 0; j < candidateToN[i].length; j++) {
                if(j>0){
                    candidateToN[i][j]=candidateToN[i][j-1]+candidateToN[i][j];
                }
            }
        }
        for (int i = 0; i < n; i++) {
            int m=Integer.MAX_VALUE;
            for (int j = 0; j < candidateToN.length; j++) {
                m=Math.min(m,candidateToN[j][i]);
            }
            ret.append(m);
            ret.append(" ");
        }
        System.out.println(ret);
    }
}

import sys

k = int(sys.stdin.readline().strip())
x = list(map(int, sys.stdin.readline().strip().split()))
y = list(map(int, sys.stdin.readline().strip().split()))
max_int = pow(2, 31)
res = [max_int]*k

for xi in x:
    for yi in y:
        temp1 = [abs(temp - xi) for temp in x]
        temp2 = [abs(temp - yi) for temp in y]
        temp = [temp1[i]+temp2[i] for i in range(k)]
        temp.sort()
        add = 0
        for t in range(len(temp)):
            add += temp[t]
            if add < res[t]:
                res[t] = add

_res = ""

for i in range(len(res)):
    _res += " {}".format(res[i])
print(_res.strip())