首页 > 试题广场 >

堆棋子

[编程题]堆棋子

热度指数：15215 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

输出

0 1 3 10

算法知识视频讲解

Java

张逐流

移动最少距离的位置一定是几个棋子中间的某个位置，所以便利每个棋子到某个位置的距离，排序。

import java.io.BufferedReader;

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int num=Integer.parseInt(br.readLine());
        String[] s1=br.readLine().split(" ");
        int[] x=new int[num];
        for(int i=0; i<num;i++) {
            x[i]=Integer.parseInt(s1[i]);
        }

        String[] s2=br.readLine().split(" ");
        int[] y=new int[num];
        for(int i=0;i<num;i++) {
            y[i]=Integer.parseInt(s2[i]);
        }

        int[] distance=new int[num];
        int[] result=new int[num];
for(int i=0;i<num;i++) {
            result[i]=Integer.MAX_VALUE;
        }
        for(int i=0;i<num;i++) {
            for(int j=0;j<num;j++) {
                for(int k=0;k<num;k++) {
                    distance[k]=Math.abs(x[k]-x[i])+Math.abs(y[k]-y[j]);
                }
                Arrays.sort(distance);
                int temp=0;
                for(int m=0;m<num;m++) {
                    temp+=distance[m];
                    result[m]=(result[m]<temp?result[m]:temp);
                }
            }
        }

        for(int i=0;i<num-1;i++) {
            System.out.print(result[i]+" ");
        }
        System.out.print(result[num-1]);
    }

}

发表于 2019-03-27 22:32:12 回复(0)

Java

成程晨

import java.util.*;
public class Main{
    /*
    之前尝试用dfs求出各种组合，再取中位数为所有棋子移动到的点，结果只通过70%测试用例，然后超时。。。
    曼哈顿距离
    思路：n个棋子，全部移动到某一点时所需的操作数最少。该点横坐标为n个棋子中横坐标之一，纵坐标为n个棋子纵坐标之一
         三维数组 dist[i][j][k] 含义：对于坐标为(x[i],y[j])的点来说，它离第k个棋子a[k]的曼哈顿距离
         三维数组的dist[i][j]所对应的棋盘上的点的横纵坐标由n个棋子的横纵坐标组合而成，因此有 n * n 种组合情况
         求得了dist[i][j][k]之后，对dist[i][j]按从小到到大排序，即按该点离各个棋子的近远排序
         当要求m个棋子位于一个坐标时，只需比较每个点上聚集m个棋子所需的最小操作数（即对于上一步排序好的dist[i][j],每一行取前m列求和），取最小即可
    */
    private static int[] min;
    public static void main(String[]  args){
        try(Scanner in = new Scanner(System.in)){
            int n = in.nextInt();
            int[] x = new int[n],y = new int[n];
            min = new int[n];
            for(int i = 0;i < n;i++){
                x[i] = in.nextInt();
            }
            for(int i = 0;i < n;i++){
                y[i] = in.nextInt();
            }
            int[][][] dist = getDist(x,y,n);
            int count = 1;
            while(count <= n){
                helper(dist,count,n);
                count++;
            }
            for(int i = 0;i < min.length - 1;i++){
                System.out.print(min[i] + " ");
            }
            System.out.println(min[min.length - 1]);
        }
    }
    public static  int[][][] getDist(int[] x,int[] y,int n){
        int[][][] dist = new int[n][n][n];
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                for(int k = 0;k < n;k++){
                    dist[i][j][k] =  Math.abs(x[k] - x[i]) + Math.abs(y[k] - y[j]);
                }
            }
        }
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                Arrays.sort(dist[i][j]);
            }
        }
        return dist;
    }
    public static void helper(int[][][] dist,int count,int n){
        int[] res = new int[n];
        int m = Integer.MAX_VALUE;
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                int sum = 0;
                for(int k = 0;k < count;k++){
                    sum += dist[i][j][k];
                }
                m = Math.min(m,sum);
            }
        }
        min[count - 1] = m;
    }
}

发表于 2019-01-14 10:52:57 回复(0)

Java

yinger553

/**
照抄别人的算法。用了好久好久。。。终于理解了。。
**/
import java.util.Arrays;
import java.util.Scanner;
public class Main{
	public static int dist(int a,int b,int c,int d) {
		return Math.abs(a-c)+Math.abs(b-d);
	}
     public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] x = new int[n];
        int[] y = new int[n];
        int[] ans = new int[n];
        int[] dis = new int[n];
        for(int i=0;i<n;i++) 
        	ans[i] = Integer.MAX_VALUE;
        for(int i=0;i<n;i++) 
        	x[i] = in.nextInt();
        for(int i=0;i<n;i++) 
        	y[i] = in.nextInt();
        
        for(int i=0;i<n;i++) {  //i,j，假设所需1,2...n个子都放在想[i],y[j]上      	
        	for(int j=0;j<n;j++) {
        		int temp = 0;
        		for(int k=0;k<n;k++) {
        			dis[k] = dist(x[k],y[k],x[i],y[j]);
        		} 
        		Arrays.sort(dis);//dis中存储任意元素x[k],y[k]与格子x[i],y[j]之间的距离。       	
        		for(int k=0;k<n;k++) {
        			temp+=dis[k];
        			ans[k] = Math.min(temp, ans[k]); 
        		}
        	}
        }
        System.out.print(ans[0]);
        for(int i=1;i<n;i++) 
        	System.out.print(" "+ans[i]); 
    }
}

编辑于 2017-09-11 14:08:34 回复(0)

Java

凯特_同学

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

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            int n = scanner.nextInt();
            int[] x = new int[n];
            int[] y = new int[n];
            int[] answer = new int[n];    
            Arrays.fill(answer, Integer.MAX_VALUE);
            for(int i = 0; i < n; i++){
                x[i] = scanner.nextInt();
            }
            for(int i = 0; i < n; i++){
                y[i] = scanner.nextInt();
            }
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    int[] array= new int[n];
                    for(int k = 0; k < n; k++){
                       array[k] = Math.abs(x[i] - x[k]) + Math.abs(y[j] - y[k]);
                    }
                    Arrays.sort(array);
                    int temp = 0;
                    for(int k = 0; k < n; k++){
                        temp += array[k];
                        answer[k] = Math.min(answer[k], temp);
                    }
                }
            }
            for(int i = 0; i < n-1; i++){
                System.out.print(answer[i] + " ");
            }
            System.out.println(answer[n-1]);
        }
        scanner.close();
    }
}

编辑于 2017-08-14 17:46:49 回复(0)

Java

lxhao

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int[] x = new int[n];
            int[] y = new int[n];
 
            for (int i = 0; i < n; i++) {
                x[i] = in.nextInt();
            }
 
            for (int i = 0; i < n; i++) {
                y[i] = in.nextInt();
            }
            List<List<Integer>> distances = new ArrayList<>();
            countDistances(x, y, distances);
            //计算至少有一个格子放i颗棋子的最小移动次数
            for (int i = 1; i <= n; i++) {
                int minMoved = Integer.MAX_VALUE;
                //计算移动i颗棋子到一个格子的最小操作次数
                for (List<Integer> disTmp : distances) {
                    int minMovedTmp = 0;
                    for (int j = 0; j < i; j++) {
                        minMovedTmp += disTmp.get(j);
                    }
                    minMoved = Math.min(minMoved, minMovedTmp);
                }
                System.out.print(minMoved);
                if(i != n) {
                    System.out.print(" ");
                }
            }
        }
    }
 
    /**
     * 最后的结果只可能出现在棋子横纵坐标的组合上
     * 比如两颗棋子的坐标为(1, 2)和(5, 6) 那最后的结果只可能出现在(1, 2),(1, 6),(5, 2),(5, 6)
     * 按总共候选点的个数就是n * n
     * 计算出所有棋子到每个候选点的距离,并对这个距离排序,根据计算出的距离选择最优解
     * 比如要求有一个格子有3颗棋子最小移动次数,只需要计算每个候选点放三颗棋子的移动次数,然后取最小值
     *
     * @param x
     * @param y
     * @param distances
     */
    private static void countDistances(int[] x, int[] y, List<List<Integer>> distances) {
        for (int i = 0; i < x.length; i++) {
            for (int j = 0; j < y.length; j++) {
                //(i,j)  为候选点
                //计算每颗棋子到候选点的距离,任意一颗棋子到(i,j)的移动次数为坐标相减取绝对值相加
                List<Integer> disTmp = new ArrayList<>();
                for (int k = 0; k < x.length; k++) {
                    disTmp.add(Math.abs(x[k] - x[i]) + Math.abs(y[k] - y[j]));
                }
                //对计算出的距离排序
                Collections.sort(disTmp);
                distances.add(disTmp);
            }
        }
    }
}

发表于 2017-08-14 10:08:28 回复(2)

Java

WayneDeng


/* 

/* 

	使用暴力枚举的方法，千万不要只考虑出现的n个点的位置，我之前就是只考虑这个，写的很简单，结果只AC 50% 


	应该要考虑这n个点附近的点，这里的解法就是考虑了所有点的横坐标上出现过纵坐标的点， 


	也就是横坐标不同数字个数*纵坐标不同的数字个数。这里的算法重复计算了相同的点，如果采用两个set集合，时间复杂度会好一点 


	*/ 


	import java.util.Arrays;
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[]X = new int[n];
		int[]Y = new int[n];
		for(int i=0;i<n;i++){
			X[i] = scan.nextInt();
		}
		for(int i=0;i<n;i++){
			Y[i] = scan.nextInt();
		}
		int[] res = new int[n];
		for(int i=0;i<n;i++){
			res[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++){
					int[] res2 = new int[n];
					for(int l=0;l<n;l++){
						res2[l] = Math.abs(X[l]-X[j])+Math.abs(Y[l]-Y[k]);
					}
					Arrays.sort(res2);
					int res3 = 0;
					for(int l=0;l<=i;l++){
						res3 = res3 + res2[l];
					}
					res[i] = Math.min(res3, res[i]);
				}
			}
		}
		for(int i=0;i<n;i++){
			if(i<n-1){
				System.out.print(res[i]+" ");
			}else{
				System.out.print(res[i]);
			}
		}
	}
}