关注
//堆棋子JAVA
import java.util.*;
public class Main{
//public static int m = 10^9; //循环边界
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int[] temp1 = new int[n];
int[] temp2 = new int[n];
//取所有初始棋子的最大边界作为循环边界(这样会超内存),不理解大佬说的为何汇聚点一定在已有棋子的横纵坐标处??
//int maxX = 0;
//int maxY = 0; //循环边界
for(int i=0; i<n; i++){
temp1[i] = sc.nextInt(); //循环边界
//maxX = Math.max(maxX,temp1[i]);
}
for(int i=0; i<n; i++){
temp2[i] = sc.nextInt();
//maxY = Math.max(maxY,temp2[i]);
}
Point[] point = new Point[n+1]; //棋子的初始位置
for(int i=0; i<n; i++){
point[i+1] = new Point(temp1[i],temp2[i]);
}
int[] shortDistance = new int[n+1]; //放置i个棋子的最少操作次数
Arrays.fill(shortDistance,Integer.MAX_VALUE);
//循环边界没取10^9,只能通过30%;取初始棋子的最大边界,通过60%。取初始棋子下标,100%
for(int i : temp1){
for(int j : temp2){
int[] distance = new int[n+1];
//在坐标(i,j)放置k个棋子
for(int k=1; k<=n; k++){ //求出(i,j)到每个初始点的距离,排序
distance[k] = Math.abs(i-point[k].x) + Math.abs(j-point[k].y);
}
Arrays.sort(distance);
int temp = 0;
//求若在(x,y)放置1~n个棋子的最短距离,更新结果集合(判断全局最短是否为在(i,j)处获得)
for(int k=1; k<=n; k++){
temp += distance[k];
shortDistance[k] = Math.min(shortDistance[k],temp);
}
}
}
for(int i=1; i<=n-1; i++){
System.out.print(shortDistance[i] + " ");
}
System.out.println(shortDistance[n]);
}
}
private static class Point{
int x;
int y;
Point(int x, int y){
this.x = x;
this.y = y;
}
}
}
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
转发
04-25 18:52
门头沟学院 电子信息类 点赞 评论 收藏
转发
昨天 20:30
北京航空航天大学 机械类 点赞 评论 收藏
转发
牛客热帖
正在热议
# 牛客帮帮团来啦!有问必答 #
384460次浏览 7645人参与
# 应届生初入职场,求建议 #
22038次浏览 537人参与
# 晒一晒我的offer #
2803813次浏览 49746人参与
# 在国企工作的人,躺平了吗? #
71810次浏览 868人参与
# 简历中的项目经历要怎么写 #
378686次浏览 6367人参与
# 非技术岗薪资爆料 #
7023次浏览 135人参与
# 你更愿意参加线上面试还是线下面试? #
6567次浏览 91人参与
# 非技术薪资爆料 #
63792次浏览 954人参与
# 华为求职进展汇总 #
439180次浏览 4417人参与
# 第一次面试 #
15815次浏览 240人参与
# 租房前辈的忠告 #
20890次浏览 1656人参与
# 应届生应该先就业还是先择业 #
12149次浏览 114人参与
# 安利/避雷我的岗位 #
122419次浏览 2752人参与
# 来聊聊机械薪资天花板是哪家 #
20970次浏览 166人参与
# 机械人怎么评价今年的华为 #
54155次浏览 444人参与
# 谈薪时HR压价该怎么应对 #
33076次浏览 204人参与
# 通信硬件薪资爆料 #
145535次浏览 1090人参与
# 毕业租房也有小确幸 #
19880次浏览 1253人参与
# 数据人offer决赛圈怎么选 #
36675次浏览 659人参与
# 正在实习的你,有转正机会吗? #
83442次浏览 866人参与