首页 > 试题广场 >

堆棋子

[编程题]堆棋子
  • 热度指数：15153 时间限制：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
算法知识视频讲解
添加回答
蟹粉馅大糖包头像 蟹粉馅大糖包 
暴力枚举法居然过了，关键在于，最后堆棋子的那个格子，横纵坐标必然在棋子初始的横纵坐
标中间
用反证法，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个坐标中考虑

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<Long> res = new ArrayList<>();
            long min, sum;
            for (int i = 1; i <= n; i ++) {
                min = Long.MAX_VALUE;
                for (int row = 0; row < n; row ++) {
                    for (int col = 0; col < n; col ++) {
                        sum = 0;
                        PriorityQueue<Integer> pq = new PriorityQueue<>(i, new Comparator<Integer>() {
                            @Override
                            public int compare(Integer o1, Integer o2) {
                                return o2 - o1;
                            }
                        });
                        for (int c = 0; c < n; c ++) {
                            int xc = x[c];
                            int yc = y[c];
                            int distance = Math.abs(xc - x[row]) + Math.abs(yc - y[col]);
                            sum += distance;
                            pq.add(distance);
                            if (pq.size() > i) {
                                sum -= pq.poll();
                            }
                        }
                        min = Math.min(min, sum);
                    }
                }
                res.add(min);
            }
            for (int i = 0; i < n - 1; i ++) System.out.print(res.get(i) + " ");
            System.out.println(res.get(n - 1));
        }
    }
}


编辑于 2017-08-12 21:13:44 回复(29)
gggv123头像 gggv123
下面的思路参考了@蟹粉馅大糖包

本题的关键是找到一个最优的聚合点，使得各个棋子到这个聚合点的距离最短。由于x和y轴是相互独立的，互不影响，因此可以先分析x轴再分析y轴。以【1，2，4，9】为例，根据@蟹粉馅大糖包的证明，最优聚合点的x坐标一定是【1，2，4，9】这几个数之一，同理y坐标一定是【1，1，1，1】这几个数之一。有了这个结论，就可以使用暴力法，一一枚举每一个可能的点并计算距离，求出距离最小的那个点。

为了证明上面的结论，我们使用反证法：

假设存在点x0使得其余各点到x0的距离最短，并且x0不是【1，2，4，9】之一。以x0=6为例，在x0左边有【1，2，4】共3个数，我们把3记为a；在x0右边有【9】共1个数，把1记为b。【1，2，4】到x0的距离记为A；【9】到x0的距离记为B；那么总距离就为A+B。

当a > b时，我们发现x0左边第一个在【1，2，4，9】集合中的数，会得到更小的距离。即：x0等于4时，总距离是：A+B-a * 2 + b * 2，其中a等于3，b等于1。所以我们之前的假设不成立~

同理，当a < b时，x0右边第一个在【1，2，4，9】集合中的数，也会使总距离变小。

这里写图片描述

当a == b时，“x0等于3”与 “x0等于2” 或者 “x0等于4”时的总距离相等，因此“x0等于3”就可以被“x0等于3”或“x0等于4”替代。

这里写图片描述

总结一下， 我们最开始的假设不成立，当x0为【1，2，4，9】之一，必可以取到最小值，同理y0应该为【1，1，1，1】之一。  -----谢谢@牛客109788号的提醒-----

有了上面的结论，就可以写出代码了，具体可见下面的博客：http://blog.csdn.net/u010429424/article/details/77198486
编辑于 2017-08-17 22:19:23 回复(9)
牛客2840146号头像 牛客2840146号 
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int n, x[55], y[55], ans[55];

void helper(){
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			int tmp = 0;
			vector<int> dis(n, 0);
			for(int k = 0; k < n; ++k) dis[k] = abs(x[i] - x[k]) + abs(y[j] - y[k]);
			std::sort(dis.begin(), dis.end());
			for(int k = 0; k < n; ++k){
				tmp += dis[k];
				ans[k] = min(ans[k], tmp);
			}
		}
	}
}

int main(int argc, char **argv){
	cin>>n;
	for(int i = 0; i < n; ++i) cin>>x[i];
	for(int i = 0; i < n; ++i) cin>>y[i];
	for(int i = 0; i < n; ++i) ans[i] = INT_MAX;
	helper();
	for(int i = 0; i < n - 1; ++i) cout<< ans[i] << " ";
	cout<< ans[n - 1];
}

发表于 2017-08-13 14:35:56 回复(10)
velong头像 velong

对蟹粉馅大糖包证明的补充
xy轴其实是独立的，先只考虑x坐标，采用反证法，假设把k个棋子堆到x0(x0不为任意一个棋子坐标)格子所用的步骤最少。
a个棋子初始在x0的左边，b个棋子初始在x0的右边.左边到x0的总距离为A,右边到x0的总距离为B.

  1. 如果a>b,那么对于最靠近x0左边的棋子坐标x[a]来说(假设x[a]与x0的距离为da,那么以x[a]坐标为基准现在的总距离为[(A+B)-da*a+da*b]<A+B，这k个棋子到x[a]的步数会更少；

  2. 同理对于b>a的情况，那么对于最靠近x0右边的棋子坐标x[b]的目标将比x0更优，

  3. 如果a=b，x[a]、x0、x[b]的步数是一样的。
因此，最终汇聚棋子的x坐标只要在棋子初始的x个坐标中考虑 

import java.util.Arrays;
import java.util.Scanner;
public class Main{
       public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        final int n=scan.nextInt();
        int []x=new int[n];
        int []y=new int[n];
        int i,j,k,l;
        for(i=0;i<n;i++)
            x[i]=scan.nextInt();
        for(j=0;j<n;j++)
            y[j]=scan.nextInt();

        long []result=new long[n];
        result[0]=0;
         //(Xj,Yk)到第i个棋子的距离，(Xi,Yi)与(Xj,Yk)为相同坐标时也要计算，此时他们的距离为0.
        long [][][]distance=new long[n][n][n];

        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                for(k=0;k<n;k++){
                    distance[j][k][i]=Math.abs(x[i]-x[j])+Math.abs(y[i]-y[k]);
                }
            }
        }
        //(Xj,Yk)到所有棋子距离从小到大排序,计算k个棋子最小距离的关键步骤，要理解为什么排序
        for(j=0;j<n;j++){
            for(k=0;k<n;k++){
                Arrays.sort(distance[j][k],0,n);
            }

        }
        //k个棋子放置一起所需要的最小距离
        for(i=1;i<n;i++){
         long min=Long.MAX_VALUE;
         for(j=0;j<n;j++){
             for(k=0;k<n;k++){
                 long curLength=0;
                 for(l=0;l<i+1;l++){
                     curLength+=distance[j][k][l];
                 }
                 min=Math.min(curLength,min);
             }

         }
            result[i]=min;
        }
        StringBuilder str=new StringBuilder();
        for(i=0;i<n;i++)
            str.append(result[i]+" ");
        str.deleteCharAt(str.length()-1);
        System.out.print(str);
      

    }
}

编辑于 2017-08-16 14:45:20 回复(2)
元气の悟空头像 元气の悟空 
//AC代码：
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
//#include<windows.h>
using namespace std;
const long INF=999999999;
int main(){
    int N,i,j,k,q;
    long x[100],y[100];
    //freopen("input.txt","r",stdin);
    while(scanf("%d",&N)!=EOF){
        for(i=0;i<N;i++) scanf("%ld",&x[i]);
        for(i=0;i<N;i++) scanf("%ld",&y[i]);
        vector<vector<int> > dis;
        for(k=0;k<N;k++)
            for(q=0;q<N;q++){
                vector<int> d;
                for(i=0;i<N;i++) d.push_back(abs(x[i]-x[k])+abs(y[i]-y[q]));
                sort(d.begin(),d.end());
                dis.push_back(d);
            }
        for(i=1;i<=N;i++){
            long Min=INF;
            for(j=0;j<dis.size();j++){
                long sum=0;
                for(k=0;k<i;k++) sum+=dis[j][k];
                Min=min(Min,sum);
            }
            printf("%d%s",Min,i==N?"\n":" ");
        }
    }
}//直接暴力，随便搞，就过了

发表于 2017-08-23 17:53:46 回复(1)
木然猫猫头像 木然猫猫
聚合点的x坐标必然是给出的x坐标之一，聚合点的y坐标必然是给出的y坐标之一。因此，n个点就有n^2个可能的聚合点。 

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> x(n, 0), y(n, 0);
    for (int i = 0; i < n; i++)
        cin >> x[i];
    for (int i = 0; i < n; i++)
        cin >> y[i];
    priority_queue<int, vector<int>, greater<int> > pq;
    vector<int> res(n, INT_MAX);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                pq.push(abs(x[k] - x[i]) + abs(y[k] - y[j]));
            }
            int tmp = 0;
            for (int k = 0; k < n; k++) {
                tmp += pq.top();
                res[k] = min(res[k], tmp);
                pq.pop();
            }
        }
    for (int i = 0; i < n; i++) {
        if (i == 0) cout << res[i];
        else cout << " " << res[i];
    }
    cout << endl;
    return 0;
}

运行时间：9ms

占用内存：468k


发表于 2019-03-16 23:41:31 回复(0)
OFShare头像 OFShare 
//思路：枚举所有棋子到每个可能的(x,y)的曼哈顿距离(见dist函数)。然后维护排序后的前k个点的最小值。
//可能的(x,y)就是:如果有旗子(x1,y1)和(x2,y2),那么所有可能的点就是(x1,y1),(x1,y2),(x2,y1),(x2,y2)
//AC源码:
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

struct Point
{
	int x=0;
	int y=0;
}A[55];

int n;
vector<vector<int> > vvec;
int dist(int x,int y,const Point& obj)
{
	return abs(x-obj.x)+abs(y-obj.y);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;++i)
		cin>>A[i].x;
	for(int i=1;i<=n;++i)
		cin>>A[i].y;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)
		{
			vector<int> tmp;
			for(int k=1;k<=n;++k)
			{
				tmp.push_back(dist(A[i].x,A[j].y,A[k]));
			}	
			sort(tmp.begin(),tmp.end());
			vvec.push_back(tmp);
		}
	}
	for(int k=1;k<=n;++k)
	{
		int ans=0x17171717;
		for(int i=0;i<vvec.size();++i)
		{
			int res=0;
			for(int j=0;j<k;++j)
				res+=vvec[i][j];
			ans=min(ans,res);
		}
		if(k==1)
			cout<<ans;
		else
			cout<<" "<<ans;
	}
	return 0;
}

发表于 2017-08-13 13:25:54 回复(4)
AlexNeverStop头像 AlexNeverStop
AC by python 
a=raw_input()
x=[int(i) for i in raw_input().split(' ')]
y=[int(j) for j in raw_input().split(' ')]
def calculatedistance(pinit1x,point1k,point2y,point2k):
    return abs(pinit1x-point1k)+abs(point2y-point2k)
ans=[6553000000]*100
for i in range(len(x)):
    for j in range(len(y)):
        lingshi=0
        tmp=[]
        for k in range(len(y)):
            tmp.append(calculatedistance(x[i],x[k],y[j],y[k]))
        tmp.sort()
        for k in range(len(y)):
            lingshi=lingshi+tmp[k]
            ans[k]=min(ans[k],lingshi)
for i in range(len(x)):
    print ans[i],


编辑于 2017-08-13 16:43:28 回复(4)
tides头像 tides 
import sys
n = int(sys.stdin.readline().strip())
x = [int(num) for num in sys.stdin.readline().strip().split()]
y = [int(num) for num in sys.stdin.readline().strip().split()]

dic = {n: float('inf') for n in range(2, len(x) + 1)}
for i in range(n):
    for j in range(n):
        dists = sorted(abs(x[p]-x[i]) + abs(y[p]-y[j]) for p in range(n))
        for j in range(1, n):
            dists[j] += dists[j-1]
        for l in range(2, n+1):
            dic[l] = min(dic[l], dists[l-1])
res = ['0'] + [str(dic[l]) for l in range(2, n + 1)]
print(' '.join(res))

发表于 2019-03-20 18:14:47 回复(0)
取什么好呢123头像 取什么好呢123 
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            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();
            }

            String res = "";
            for (int i = 1; i <= n; i++) {
                int min = Integer.MAX_VALUE;
                // 遍历所以可能情况
                for (int row = 0; row < n; row++) {
                    for (int col = 0; col < n; col++) {
                        int[] dis = new int[n];
                        // 计算当前可能点到其他点的距离
                        for (int j = 0; j < n; j++) {
                            dis[j] = Math.abs(x[row] - x[j]) + Math.abs(y[col] - y[j]);
                        }
                        Arrays.sort(dis);

                        int sum = 0;
                        for (int j = 0; j < i; j++) {
                            sum += dis[j];
                        }
                        min = Math.min(min, sum);
                    }
                }
                res = res + min + " ";
            }
            System.out.println(res.trim());
        }
    }
}

发表于 2017-08-17 21:21:49 回复(0)
C/C++
京木027头像 京木027
最开始并没有做出来，听了左神讲解后才懂的。
思路：
1 一维情况：若干个点，一定是选择某聚合点，使得左右两边的点数相同时移动成本最小。奇数个点时肯定是中间点作为聚合点，偶数个点时一定是在中间两个点之间包括中问两个点。因此，得到结论：聚合点一定是若干个点中的某个点。
2 二维情况，xy轴的移动成本是各自独立的，可直接求得聚合点坐标{x,y}。但是结论同样成立：聚合点一定是在XY的笛卡尔积中。
3 当然，如果只是求所有点移动到同一点的成本，那么可以直接求得聚合点的{x,y}坐标，进而得到总移动成本。但是现在需要求从1个点到N个点移动到同一点的成本，当1<n<N时，涉及到组合优化问题，所以我们在笛卡尔积中找最优解而不是直接求得指定点的聚合点坐标。

代码如下： 
#include <iostream>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

class Solution{
private:
    int num_nodes;
    vector<int> xcoors;
    vector<int> ycoors;
    vector<int> res;

private:
    void init(){
        cin>>num_nodes;
        xcoors.resize(num_nodes);
        ycoors.resize(num_nodes);
        res.resize(num_nodes,INT_MAX);
        for(int i=0;i<num_nodes;i++)
            cin>>xcoors[i];
        for(int i=0;i<num_nodes;i++)
            cin>>ycoors[i];
    }
    void write_result(){
        if(res.empty()==false)
            cout<<res.front();
        for(int i=1;i<num_nodes;i++)
            cout<<" "<<res[i];
    }
    void calculate_result(){
        for(int ix=0;ix<num_nodes;ix++){
            int x=xcoors[ix];
            for(int iy=0;iy<num_nodes;iy++){
                int y=ycoors[iy];
                update_result(x,y);
            }
        }
    }
    void update_result(int x,int y){
        priority_queue<int,vector<int>,greater<int>> pq;
        for(int i=0;i<num_nodes;i++)
            pq.push(abs(x-xcoors[i])+abs(y-ycoors[i]));
        int sum=0;
        for(int i=0;i<num_nodes;i++){
            sum+=pq.top();
            pq.pop();
            if(sum<res[i])
                res[i]=sum;
        }
    }

public:
    void solve(){
        init();
        calculate_result();
        write_result();
    }
};

int main()
{
    Solution s;
    s.solve();

    return 0;
}


发表于 2017-08-31 16:54:08 回复(2)
秋丶舞霜头像 秋丶舞霜
最少移动的点是XY 的中位数
发表于 2017-08-13 13:16:26 回复(6)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    int x[n], y[n], r[n];
    fill(r, r+n, INT_MAX);
    for(int i=0;i<n;i++)
        scanf("%d", &x[i]);
    for(int i=0;i<n;i++)
        scanf("%d", &y[i]);
    
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            int t = 0, d[n]={0};
            for(int k=0;k<n;k++)
                d[k] = abs(x[k]-x[i]) + abs(y[k]-y[j]);
            sort(d, d+n);
            for(int k=0;k<n;k++){
                t += d[k];
                r[k] = min(r[k], t);
            }
        }

    for(int i=0;i<n;i++){
        if(i==n-1)
            printf("%d\n", r[i]);
        else
            printf("%d ", r[i]);
    }
    return 0;
}

发表于 2020-09-26 08:34:03 回复(0)
Yumho头像 Yumho
最优聚合点的横坐标一定是 x 这几个数之一，纵坐标坐标一定是y这几个数之一。
使用 set，然后暴力枚举即可 
n = int(input())
x = list(map(int, input().strip().split()))
y = list(map(int, input().strip().split()))

nodex = set(x)
nodey = set(y)


def distance(x0, y0, x1, y1):
    return abs(x0 - x1) + abs(y0 - y1)


res = []
for nx in nodex:
    for ny in nodey:
        temp = []
        for k in range(n):
            temp.append(distance(nx, ny, x[k], y[k]))
        temp.sort()
        for k in range(1, n):
            temp[k] += temp[k - 1]
        res.append(temp)

print(' '.join(str(min(col)) for col in zip(*res)))

编辑于 2019-08-06 22:02:05 回复(0)
向宇回桌头像 向宇回桌
可能有多个最优点。但必然有一个最优点，在x[i]和y[j]的组合点上。所以，枚举这个点，就可以了。 
import java.util.*;
public class Main {
    private static final int MAX = 50 + 5;
    private static final int INT_MAX = 0x3f3f3f3f;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] x = new int[MAX], y = new int[MAX];
        for (int i=1; i<=n; i++) {
            x[i] = sc.nextInt();
        }
        for (int i=1; i<=n; i++) {
            y[i] = sc.nextInt();
        }
        int[] ans = new int[MAX];
        Arrays.fill(ans, INT_MAX);
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++) {
                int target_x = x[i], target_y = y[j];
                int[] distances = new int[MAX];
                for (int k=1; k<=n; k++) {
                    distances[k] = Math.abs(target_x-x[k]) + Math.abs(target_y-y[k]);
                }
                Arrays.sort(distances, 1, n+1);
                for (int range = 1; range<=n; range++) {
                    int sum = 0;
                    for (int p=1; p<=range; p++) {
                        sum += distances[p];
                    }
                    ans[range] = Math.min(ans[range], sum);
                }
            }
        }
        for (int i=1; i<=n; i++) {
            System.out.printf("%d ", ans[i]);
        }
    }
}
发表于 2019-01-20 19:50:34 回复(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)
果壳头像 果壳 
/*很简洁很漂亮很强大的代码，只有三个长度为n的数组为全局变量，一个长度为n的数组为局部变量。
只要遍历n*n个点即可，算出每一个点到1至n个点的最短路径，只保留最小值，便历完后输出。
一开始也走了很多弯路，代码改了好久，之前考虑扫描一个矩阵，结果内存总是超，
在现有代码基础上做小幅度修改就可以，这个算法不用存储较大的数组，不知道为什么会超内存？
如果存在目标点x，y与现有的点无交集，那这个算法就不能通过。
*/
import java.util.Arrays;
import java.util.Scanner;

public class Shortdis {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[] a = new int[n];
		int[] b = new int[n];
		for (int i = 0; i < n; i++) {
                    a[i] = sc.nextInt();
                }
		sc.nextLine();
		for (int i = 0; i < n; i++) {
                    b[i] = sc.nextInt();
                }
		sc.close();
		int[] re=new int [n];
		for(int m=0;m<n;m++){//从某个空格有1个子到n个子，然后输出。
			for(int j=0;j<n;j++){//扫描所有点的x坐标。
				for(int k=0;k<n;k++){//扫描所有点的y坐标。
					int[] c=new int [n];//存放临时数据。
					for(int i=0;i<n;i++){//分别计算某个点到所有点的距离。
						c[i]=Math.abs(a[j]-a[i])+Math.abs(b[k]-b[i]);
					}
					Arrays.sort(c);//排序。
					for(int l=1;l<n;l++){//到n个点的最小路径。
						c[l]+=c[l-1];
					}
					if(j==0&&k==0){
						for(int i=0;i<n;i++){
							re[i]=c[i];
						}
					}
					for(int i=0;i<n;i++){//存放临时数据。
						if(c[i]<re[i]){
							re[i]=c[i];
						}
					}
				}			
			}
			if(m>0){
				System.out.print(" ");
			}
			System.out.print(re[m]);//输出。
		}
	}
}


发表于 2017-09-08 10:32:04 回复(0)
哈哈哈_哈喽头像 哈哈哈_哈喽 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * 
 * @author HeMing
 *
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = 0;
        long[] x = null;
        long[] y = null;
        while (in.hasNextInt()) {//注意while处理多个case
            n = in.nextInt();
            x = new long[n];
            y = new long[n];
            for (int i=0; i<n; i++) {
                int xi =in.nextInt();
                x[i] = xi;    
            }
            for (int i=0; i<n; i++) {
                int yi =in.nextInt();
                y[i] = yi;
            }
            
            /**第一步:
             * 计算Xi，Yj点到各个初始点Xk,Yk的距离，并从小到大排序后存入list*/
            List<long[]> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                for  (int j = 0; j < n; j++) {
                	long[] currDistances = new long[n];
                    for (int k = 0; k < n; k++) {
                    	currDistances[k] = Math.abs(x[i]-x[k]) + Math.abs(y[j]-y[k]);
                    }
                    Arrays.sort(currDistances);
                    list.add(currDistances);
                }
            }
            /**
             * 第二步:
             * 计算list中每一个数组中的前k+1(k从0开始)个数的和,求出result*/
            long[] result = new long[n];
            //lastSum表示前一次计算中的sum结果数组，避免重复计算
            long[] lastSum = new long[list.size()];
            for (int k = 0; k < n; k++) {
            	long min = Long.MAX_VALUE;
            	for (int i = 0; i < list.size(); i++) {
            		lastSum[i] += list.get(i)[k];
            		min = Math.min(min, lastSum[i]);
            	}
            	result[k] = min;
            }
            
            StringBuilder sb = new StringBuilder();
            for (long singleResult : result) {
                sb.append(singleResult + " ");
            }
            sb.deleteCharAt(sb.length()-1);
            //输出
            System.out.println(sb);
        }
 
    }
}
发表于 2017-08-17 17:26:52 回复(0)
Yabi胖要刷题头像 Yabi胖要刷题 
//参考别人写的，其实很简单，想通了特别简单，为什么总是写小bug
//https://www.nowcoder.com/discuss/32162--感谢乐于分享的你们
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
    {
    int n;
    cin>>n;
    vector<int> x(n);
    vector<int> y(n);
    for(int i=0;i<n;i++)
        cin>>x[i];
    for(int i=0;i<n;i++)
        cin>>y[i];
    vector<vector<int> > dist;//存储Manhattan距离
    for(int i=0;i<n;i++)
        {
        for(int j=0;j<n;j++)
            {
             vector<int> d(n,0);
             for(int k=0;k<n;k++)
                  d[k]=abs(x[i]-x[k])+abs(y[j]-y[k]);
             sort(d.begin(),d.end());
             for(int k=1;k<n;k++)
                  d[k]=d[k]+d[k-1];
             dist.push_back(d);
            }
       }//构建完毕表格
   //开始求第i个
    int minx;
    for(int i=0;i<n;i++)
    {//求第i+1列的最小值
        minx=1000000000;
        for(int j=0;j<n*n;j++)
           {
             if(dist[j][i]<minx)
                 minx=dist[j][i];
           }
        if(i<n-1)
           cout<<minx<<" ";
    }
    cout<<minx;
}
发表于 2017-08-15 21:33:01 回复(1)
云中的承诺头像 云中的承诺 
 a=raw_input() 
  x=[int(i) for i in raw_input().split()] 
 
  y=[int(j) for j in raw_input().split()] 
 
  z = [] 
 
  def calculatedistance(pinit1x,point1k,point2y,point2k): 
 
   return abs(pinit1x-point1k)+abs(point2y-point2k) 
 
  ans=[6553000000]*100 
 
  for i in range(len(x)): 
 
   for j in range(len(y)): 
 
   lingshi=0 
 
   tmp=[] 
 
   for k in range(len(y)): 
 
   tmp.append(calculatedistance(x[i],x[k],y[j],y[k])) 
 
   tmp.sort() 
 
   for k in range(len(y)): 
 
   lingshi=lingshi+tmp[k] 
 
   ans[k]=min(ans[k],lingshi) 
 
  for i in range(len(x)): 
 
   z.append(str(ans[i])) 
 
  print ' '.join(z) 

                                                                                    



                                        

                                            
                                                                                                                                                            发表于  2017-08-15 15:51:42
                                                    
                                                                                            
                                                回复(1)
                                                                                                                                            

                                        

                                


                                                            
                        

                        
                                        

                            

        


                    

                                    

                        

                            

                            

                                提交观点
                            

                        

                    

                            

            

    

          

            
问题信息

            

              

                                      C++工程师
                                      golang工程师
                                      iOS工程师
                                      安卓工程师
                                      运维工程师
                                      前端工程师
                                      算法工程师
                                      测试工程师
                                      PHP工程师
                                      模拟
                                      网易
                                      2018
                                      Java工程师
                                

                                  

                    来自：网易2018校招内推编...
                  

                
                                                      

                          上传者：小小
                      

                                              

                                        难度：

                                

                                        61条回答
                      
                      20461浏览
                                

            

          

            




















                    

            

                        

  

    

      
      
      
    

    
热门推荐

  

  

    

      
    

  



            

                

            

          
                          

                

                  
通过挑战的用户

                                          查看代码
                                    

                

                  
                

              

                        

                          

                
相关试题

                

                  
                

              

            
                            

                        堆棋子
                

                





                
        

                                                                

        

    
    
    

    


            
    
    

        

            

                
            

            
扫一扫，把题目装进口袋

        

        

            
求职之前，先上牛客

            

                
                    

                        

                        

                            
                            
扫描二维码，进入QQ群

                        

                    

                
                
                    

                        

                        

                            
                            
扫描二维码，关注牛客公众号