765      阿裏雲  技術社區[雲棲]

網易2018校招內推編程題 堆棋子

* 問題

小易將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

 *

標中間

用反證法，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個坐標中考慮”

所以，隻需要計算如下圖紅色線的交叉點距離所有棋子的距離。

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);
	}
}

最後更新：2017-09-08 09:02:44

  上一篇：  網易2018校招內推編程題 獨立的小易

  下一篇：  用IDEA基於maven項目使用mybatis-generator-plugin生成mapper和pojo