* 问题

小易将n个棋子摆放在一张无限大的棋盘上。第i个棋子放在第x[i]行y[i]列。同一个格子允许放置多个棋子。

每一次操作小易可以把一个棋子拿起并将其移动到原格子的上、下、左、右的任意一个格子中。小易想知

道要让棋盘上出现有一个格子中至少有i(1 ≤ i ≤ n)个棋子所需要的最少操作次数.

输入描述:

输入包括三行,第一行一个整数n(1 ≤ n ≤ 50),表示棋子的个数

第二行为n个棋子的横坐标x[i](1 ≤ x[i] ≤ 10^9)

第三行为n个棋子的纵坐标y[i](1 ≤ y[i] ≤ 10^9)

输出描述:

输出n个整数,第i个表示棋盘上有一个格子至少有i个棋子所需要的操作数,以空格分割。行末无空格

如样例所示:

对于1个棋子: 不需要操作

对于2个棋子: 将前两个棋子放在(1, 1)中

对于3个棋子: 将前三个棋子放在(2, 1)中

对于4个棋子: 将所有棋子都放在(3, 1)中

输入例子1:

4

1 2 4 9

1 1 1 1

输出例子1:

0 1 3 10

 * 思路：

 * 这题一开始想错误，首先用的暴力算法，对每个x坐标 xMin<=x<=xMax  y坐标 yMin<=y<=yMax 的点，全部都求一遍到这n个棋子点的距离。

 * 如上图 红色包围区域为需要计算点的范围

 * 结果程序内存超标

 * 修改了内存占用之后，时间又超标。 

 * 后来在牛客网看到了@蟹粉馅大糖包  的分析：

 * “暴力枚举法居然过了，关键在于，最后堆棋子的那个格子，横纵坐标必然在棋子初始的横纵坐

标中间

用反证法，xy轴其实是独立的，先只考虑x坐标，假设把k个棋子堆到x0格子所用的步骤最少，

a个棋子初始在x0的左边，b个棋子初始在x0的右边，且a>b,那么必然存在横坐标为x0-1的格

子，这k个棋子到x0-1的步数会更少，b>a的情况，那么x0+1的目标将比x0更优，至于a=b，

x0-1 和x0的步数是一样的。因此，最终汇聚棋子的x坐标只要在棋子初始的x个坐标中考虑”

所以，只需要计算如下图红色线的交叉点距离所有棋子的距离。

java代码：

public class PilePieces {
	
	public static int n;
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		int[] xArr = new int[n];
		int[] yArr = new int[n];
		int[] result=new int[n];//存放最终结果的数组，result[0]初始化为0，其余初始化为Integer.MAX_VALUE;
		for (int i = 0; i < n; i++) {
			if(i!=0)
				result[i]=Integer.MAX_VALUE;
			xArr[i]=scanner.nextInt();
		}
		for (int i = 0; i < n; i++) {
			yArr[i]=scanner.nextInt();
		}
	
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int[] arrTemp=new int[n];//临时数组，用来记录点(xArr[i],yArr[j])到第j2个棋子的距离。
				for (int j2 = 0; j2 < n; j2++) {
					int xDis=xArr[j2]-xArr[i];//取x轴的差
					int yDis=yArr[j2]-yArr[j];//取y轴的差
					xDis=xDis<0?-xDis:xDis;//取正距离
					yDis=yDis<0?-yDis:yDis;//取正距离
					arrTemp[j2]=xDis+yDis;//距离实际上是x轴方向的距离与y轴方向的距离之和。
				}
				Utils.getInstance().sortSmallToBig(arrTemp, 0, n-1);//对点(xArr[i],yArr[j])的距离数组进行从小到大排序。
//				对排序好的临时数组求前k项和，即是点(xArr[i],yArr[j])到最近k个棋子的距离。
//				也就是把k个棋子移动到该点所需要的最少步数。
				for (int k = 1; k < n; k++) {
					int count=0;//最少步数
					for (int k2 = 0; k2 <= k; k2++) {
						count+=arrTemp[k2];
					}
//					将最少步数和结果数组的相应位置比较，如果比他小，则将最少步数赋给结果数组相应位置。
					if(count<result[k])
						result[k]=count;
				}
			}
		}
			
//		输出结果
		for (int i = 0; i < n-1; i++) {
			System.out.print(result[i]+" ");
		}
		System.out.print(result[n-1]);	
	}	
}

class Utils{
	public static Utils sort=new Utils();
	private Utils(){	
	}
	
	public static Utils getInstance(){
		return sort;
	}
//	smallToBig和sortSmallToBig是快速排序。 针对数组进行从小到大的排序， 
//	调用 sortSmallToBig(int[] array, int start, int end)  传入数组  0  和数组.lenth-1.
	private int smallToBig(int[] array, int start, int end) {
		int key = array[start];
		while (start < end) {
			while (array[end] >= key && end > start) {
				end--;
			}
			array[start] = array[end];
			while (array[start] <= key && end > start) {
				start++;
			}
			array[end] = array[start];
		}
		array[end] = key;
		return end;
	}

	public void sortSmallToBig(int[] array, int start, int end) {
		if (start >= end) {
			return;
		}
		int local = smallToBig(array, start, end);
		sortSmallToBig(array, start, local - 1);
		sortSmallToBig(array, local + 1, end);
	}
}