java编程C村住着n户村民，由于交通闭塞，C村的村民只能通过信件与外界交流。为了方便村民们发信，C村打算在C村建设k个
java编程
C村住着n户村民，由于交通闭塞，C村的村民只能通过信件与外界交流。为了方便村民们发信，C村打算在C村建设k个邮局，这样每户村民可以去离自己家最近的邮局发信。
现在给出了m个备选的邮局，请从中选出k个来，使得村民到自己家最近的邮局的距离和最小。其中两点之间的距离定义为两点之间的直线距离。
【输入格式】
输入的第一行包含三个整数n, m, k，分别表示村民的户数、备选的邮局数和要建的邮局数。
接下来n行，每行两个整数x, y，依次表示每户村民家的坐标。
接下来m行，每行包含两个整数x, y，依次表示每个备选邮局的坐标。
在输入中，村民和村民、村民和邮局、邮局和邮局的坐标可能相同，但你应把它们看成不同的村民或邮局。
【输出格式】
输出一行，包含k个整数，从小到大依次表示你选择的备选邮局编号。（备选邮局按输入顺序由1到m编号）
【样例输入】
5 4 2
0 0
2 0
3 1
3 3
1 1
0 1
1 0
2 1
3 2
【样例输出】
2 4
【数据规模和约定】
对于30%的数据，1<=n<=10，1<=m<=10，1<=k<=5；
对于60%的数据，1<=m<=20；
对于100%的数据，1<=n<=50，1<=m<=25，1<=k<=10。
【资源约定】
峰值内存消耗 < 64M
CPU消耗 < 3000ms
C村住着n户村民，由于交通闭塞，C村的村民只能通过信件与外界交流。为了方便村民们发信，C村打算在C村建设k个邮局，这样每户村民可以去离自己家最近的邮局发信。
现在给出了m个备选的邮局，请从中选出k个来，使得村民到自己家最近的邮局的距离和最小。其中两点之间的距离定义为两点之间的直线距离。
【输入格式】
输入的第一行包含三个整数n, m, k，分别表示村民的户数、备选的邮局数和要建的邮局数。
接下来n行，每行两个整数x, y，依次表示每户村民家的坐标。
接下来m行，每行包含两个整数x, y，依次表示每个备选邮局的坐标。
在输入中，村民和村民、村民和邮局、邮局和邮局的坐标可能相同，但你应把它们看成不同的村民或邮局。
【输出格式】
输出一行，包含k个整数，从小到大依次表示你选择的备选邮局编号。（备选邮局按输入顺序由1到m编号）
【样例输入】
5 4 2
0 0
2 0
3 1
3 3
1 1
0 1
1 0
2 1
3 2
【样例输出】
2 4
【数据规模和约定】
对于30%的数据，1<=n<=10，1<=m<=10，1<=k<=5；
对于60%的数据，1<=m<=20；
对于100%的数据，1<=n<=50，1<=m<=25，1<=k<=10。
【资源约定】
峰值内存消耗 < 64M
CPU消耗 < 3000ms
赞 缘来亦逍遥 幼苗
共回答了16个问题采纳率：87.5% 举报
我编写了一个，按照样例输入但输出不同，是2,3而不是2,4，我检测了很多遍，代码没有错。完整代码我粘在下面，我把检测的代码注释了，你可以利用我注释的输出看每一步的计算过程。如有错误还望指出，希望能帮到您！import java.awt.Point;
import java.util.*;
public class Test {
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
List ns = new ArrayList(); //村民家的坐标的数组
List ms = new ArrayList(); //邮局坐标的数组
List distances = new ArrayList();//每个邮局与所有村民家的距离的数组
int[] ks;//选择的备选邮局编号的数组
int n, m, k, x, y;
double distance, min;
System.out.print("请依次输入村民户数、备选邮局数以及要建的邮局数：");
n = reader.nextInt();
m = reader.nextInt();
k = reader.nextInt();
ks = new int[k];
System.out.println("请依次输入每个村民家的坐标：");
for(int i = 0; i < n; i ++) {
Point t = new Point();
x = reader.nextInt();
y = reader.nextInt();
t.setLocation(x, y);
ns.add(t);
}
System.out.println("请依次输入每个备选邮局的坐标：");
for(int i = 0; i < m; i ++) {
Point t = new Point();
x = reader.nextInt();
y = reader.nextInt();
t.setLocation(x, y);
ms.add(t);
}
for(int i = 0; i < ms.size(); i ++) {
distance = 0;
Point po = new Point();
po = ms.get(i);
for(int j = 0; j < ns.size(); j ++) {
Point vh = new Point();
vh = ns.get(j);
//System.out.println("pX:" + po.getX() + " pY:" + po.getY() + " vX:" + vh.getX() + " vY:" + vh.getY());
//System.out.println(Math.sqrt(Math.pow(po.getX() - vh.getX(), 2)+ Math.pow(po.getY() - vh.getY(), 2)));
distance += Math.sqrt(Math.pow(po.getX() - vh.getX(), 2)+ Math.pow(po.getY() - vh.getY(), 2));
//System.out.println(distance);
}
//System.out.println("---------------------------------------------");
distances.add(distance);
}
//System.out.println("------------");
for(int i = 0 ; i < k ; i ++) {
min = distances.get(0).doubleValue();
//System.out.println(min + "n");
for (int j = 1; j < distances.size(); j++) {
if(distances.get(j).doubleValue() < min)
min = distances.get(j).doubleValue();
//System.out.println(j + " " + min);
}
ks[i] = distances.indexOf(new Double(min)) + 1;
//System.out.println(" " + (ks[i]) + " " + distances.get(ks[i]-1));
distances.set(ks[i]-1, 32700.0);
}
Arrays.sort(ks);
System.out.println("n输出结果：");
for (int i = 0; i < ks.length; i++) {
System.out.print(ks[i] + " ");
}
}
import java.util.*;
public class Test {
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
List
List
List
int[] ks;//选择的备选邮局编号的数组
int n, m, k, x, y;
double distance, min;
System.out.print("请依次输入村民户数、备选邮局数以及要建的邮局数：");
n = reader.nextInt();
m = reader.nextInt();
k = reader.nextInt();
ks = new int[k];
System.out.println("请依次输入每个村民家的坐标：");
for(int i = 0; i < n; i ++) {
Point t = new Point();
x = reader.nextInt();
y = reader.nextInt();
t.setLocation(x, y);
ns.add(t);
}
System.out.println("请依次输入每个备选邮局的坐标：");
for(int i = 0; i < m; i ++) {
Point t = new Point();
x = reader.nextInt();
y = reader.nextInt();
t.setLocation(x, y);
ms.add(t);
}
for(int i = 0; i < ms.size(); i ++) {
distance = 0;
Point po = new Point();
po = ms.get(i);
for(int j = 0; j < ns.size(); j ++) {
Point vh = new Point();
vh = ns.get(j);
//System.out.println("pX:" + po.getX() + " pY:" + po.getY() + " vX:" + vh.getX() + " vY:" + vh.getY());
//System.out.println(Math.sqrt(Math.pow(po.getX() - vh.getX(), 2)+ Math.pow(po.getY() - vh.getY(), 2)));
distance += Math.sqrt(Math.pow(po.getX() - vh.getX(), 2)+ Math.pow(po.getY() - vh.getY(), 2));
//System.out.println(distance);
}
//System.out.println("---------------------------------------------");
distances.add(distance);
}
//System.out.println("------------");
for(int i = 0 ; i < k ; i ++) {
min = distances.get(0).doubleValue();
//System.out.println(min + "n");
for (int j = 1; j < distances.size(); j++) {
if(distances.get(j).doubleValue() < min)
min = distances.get(j).doubleValue();
//System.out.println(j + " " + min);
}
ks[i] = distances.indexOf(new Double(min)) + 1;
//System.out.println(" " + (ks[i]) + " " + distances.get(ks[i]-1));
distances.set(ks[i]-1, 32700.0);
}
Arrays.sort(ks);
System.out.println("n输出结果：");
for (int i = 0; i < ks.length; i++) {
System.out.print(ks[i] + " ");
}
}
1年前
5
可能相似的问题
-
1年前1个回答
-
1年前1个回答
-
1年前1个回答
-
1年前1个回答
-
1年前1个回答
-
1年前1个回答
-
1年前1个回答
-
1年前1个回答
-
1年前1个回答
-
1年前1个回答
-
1年前1个回答
-
1年前1个回答
-
1年前1个回答
-
1年前1个回答
-
1年前1个回答
-
1年前1个回答
你能帮帮他们吗