邮局——————>算法分析

   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 3

      

       分析题目知道，此题要求在输入的m个邮局坐标求出离n个用户家距离和最近的k个坐标编号，并且有严格的输入输出要求。

两点之间线段最短：

利用此公式，代码如下：

1. 
   
2. <FONT color=#000000>package ClassPackage;
   
3. 
   
4. import java.io.BufferedReader;
   
5. import java.io.InputStreamReader;
   
6. 
   
7. public class Test19 {
   
8. public static void main(String args[])throws Exception
   
9. {
   
10. //输入n,m,k的值，并分别放入num[0]、num[1]、num[2]中
    
11. BufferedReader buf =new BufferedReader(new InputStreamReader(System.in));
    
12. String str[]=buf.readLine().split(" ");
    
13. int num[]=new int[str.length];
    
14. int i;
    
15. for(i=0;i<num.length;i++)
    
16. {
    
17. num[i]=Integer.parseInt(str[i]);
    
18. }
    
19. 
    
20. //定义居民坐标存放地址
    
21. int resident[][]=new int[num[0]][2];
    
22. //定义邮局坐标存放地址
    
23. int post[][]=new int[num[1]][2];
    
24. 
    
25. //输入n组用户坐标
    
26. for(i=0;i<num[0];i++)
    
27. {
    
28. String temp[]=buf.readLine().split(" ");
    
29. resident[i][0]=Integer.parseInt(temp[0]);
    
30. resident[i][1]=Integer.parseInt(temp[1]);
    
31. }
    
32. 
    
33. //输入m组邮局坐标
    
34. for(i=0;i<num[1];i++)
    
35. {
    
36. String temp[]=buf.readLine().split(" ");
    
37. post[i][0]=Integer.parseInt(temp[0]);
    
38. post[i][1]=Integer.parseInt(temp[1]);
    
39. }
    
40. 
    
41. //分别计算出m组邮局到n组居民间的各自距离和，放入sum中
    
42. int sum[]=new int[num[1]];
    
43. for(i=0;i<num[1];i++)
    
44. {
    
45. for(int j=0;j<num[0];j++)
    
46. {
    
47. sum[i]+=Math.sqrt(Math.pow(resident[j][0]-post[i][0],2)+Math.pow(resident[j][1]-post[i][1],2));
    
48. }
    
49. }
    
50. 
    
51. int temp1,temp2;
    
52. //由于题目要求备选邮局按输入顺序由1到m编号，将编号保存在flag[]中
    
53. int flag[]=new int[num[1]];
    
54. for(i=0;i<flag.length;i++)
    
55. flag[i]=i+1;
    
56. 
    
57. //要求输出距离和最短的前K个邮局编号，所以在此由小到大排序，并对应各自的编号
    
58. for(i=0;i<sum.length-1;i++)
    
59. for(int j=i+1;j<sum.length;j++)
    
60. {
    
61. if(sum[i]>sum[j])
    
62. {
    
63. temp2=flag[i];
    
64. flag[i]=flag[j];
    
65. flag[j]=temp2;
    
66. 
    
67. temp1=sum[i];
    
68. sum[i]=sum[j];
    
69. sum[j]=temp1;
    
70. }
    
71. }
    
72. 
    
73. /*
    
74. 此时已经获得K个邮局最短距离和，但是在输出编号时也是由小到大输出的，所以
    
75. 我们需将K个编号也进行由小到大排序
    
76. */
    
77. for(i=0;i<num[2]-1;i++)
    
78. {
    
79. for(int j=i+1;j<num[2];j++)
    
80. {
    
81. if(flag[i]>flag[j])
    
82. {
    
83. temp2=flag[i];
    
84. flag[i]=flag[j];
    
85. flag[j]=temp2;
    
86. }
    
87. 
    
88. }
    
89. 
    
90. }
    
91. //输出距离和最短的k个编号
    
92. for(i=0;i<num[2];i++)
    
93. System.out.print(flag[i]+" ");
    
94. System.out.println();
    
95. }
    
96. 
    
97. }
    
98. </FONT>

复制代码

运行结果测试：

邮局——————>算法分析

   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 3

      

       分析题目知道，此题要求在输入的m个邮局坐标求出离n个用户家距离和最近的k个坐标编号，并且有严格的输入输出要求。

两点之间线段最短：

利用此公式，代码如下：

1. 
   
2. <FONT color=#000000>package ClassPackage;
   
3. 
   
4. import java.io.BufferedReader;
   
5. import java.io.InputStreamReader;
   
6. 
   
7. public class Test19 {
   
8. public static void main(String args[])throws Exception
   
9. {
   
10. //输入n,m,k的值，并分别放入num[0]、num[1]、num[2]中
    
11. BufferedReader buf =new BufferedReader(new InputStreamReader(System.in));
    
12. String str[]=buf.readLine().split(" ");
    
13. int num[]=new int[str.length];
    
14. int i;
    
15. for(i=0;i<num.length;i++)
    
16. {
    
17. num[i]=Integer.parseInt(str[i]);
    
18. }
    
19. 
    
20. //定义居民坐标存放地址
    
21. int resident[][]=new int[num[0]][2];
    
22. //定义邮局坐标存放地址
    
23. int post[][]=new int[num[1]][2];
    
24. 
    
25. //输入n组用户坐标
    
26. for(i=0;i<num[0];i++)
    
27. {
    
28. String temp[]=buf.readLine().split(" ");
    
29. resident[i][0]=Integer.parseInt(temp[0]);
    
30. resident[i][1]=Integer.parseInt(temp[1]);
    
31. }
    
32. 
    
33. //输入m组邮局坐标
    
34. for(i=0;i<num[1];i++)
    
35. {
    
36. String temp[]=buf.readLine().split(" ");
    
37. post[i][0]=Integer.parseInt(temp[0]);
    
38. post[i][1]=Integer.parseInt(temp[1]);
    
39. }
    
40. 
    
41. //分别计算出m组邮局到n组居民间的各自距离和，放入sum中
    
42. int sum[]=new int[num[1]];
    
43. for(i=0;i<num[1];i++)
    
44. {
    
45. for(int j=0;j<num[0];j++)
    
46. {
    
47. sum[i]+=Math.sqrt(Math.pow(resident[j][0]-post[i][0],2)+Math.pow(resident[j][1]-post[i][1],2));
    
48. }
    
49. }
    
50. 
    
51. int temp1,temp2;
    
52. //由于题目要求备选邮局按输入顺序由1到m编号，将编号保存在flag[]中
    
53. int flag[]=new int[num[1]];
    
54. for(i=0;i<flag.length;i++)
    
55. flag[i]=i+1;
    
56. 
    
57. //要求输出距离和最短的前K个邮局编号，所以在此由小到大排序，并对应各自的编号
    
58. for(i=0;i<sum.length-1;i++)
    
59. for(int j=i+1;j<sum.length;j++)
    
60. {
    
61. if(sum[i]>sum[j])
    
62. {
    
63. temp2=flag[i];
    
64. flag[i]=flag[j];
    
65. flag[j]=temp2;
    
66. 
    
67. temp1=sum[i];
    
68. sum[i]=sum[j];
    
69. sum[j]=temp1;
    
70. }
    
71. }
    
72. 
    
73. /*
    
74. 此时已经获得K个邮局最短距离和，但是在输出编号时也是由小到大输出的，所以
    
75. 我们需将K个编号也进行由小到大排序
    
76. */
    
77. for(i=0;i<num[2]-1;i++)
    
78. {
    
79. for(int j=i+1;j<num[2];j++)
    
80. {
    
81. if(flag[i]>flag[j])
    
82. {
    
83. temp2=flag[i];
    
84. flag[i]=flag[j];
    
85. flag[j]=temp2;
    
86. }
    
87. 
    
88. }
    
89. 
    
90. }
    
91. //输出距离和最短的k个编号
    
92. for(i=0;i<num[2];i++)
    
93. System.out.print(flag[i]+" ");
    
94. System.out.println();
    
95. }
    
96. 
    
97. }
    
98. </FONT>

复制代码

运行结果测试：