ACM练习实战(二)

最近做了一道和中位点有关的问题,不算是非常难的题目

题目如下

 

描述
一个街区有很多住户,街区的街道只能为东西、南北两种方向。

住户只可以沿着街道行走。

各个街道之间的间隔相等。

用(x,y)来表示住户坐在的街区。

例如(4,20),表示用户在东西方向第4个街道,南北方向第20个街道。

现在要建一个邮局,使得各个住户到邮局的距离之和最少。

求现在这个邮局应该建在那个地方使得所有住户距离之和最小;

输入
第一行一个整数n<20,表示有n组测试数据,下面是n组数据;
每组第一行一个整数m<20,表示本组有m个住户,下面的m行每行有两个整数0<x,y<100,表示某个用户所在街区的坐标。
m行后是新一组的数据;
输出
每组数据输出到邮局最小的距离和,回车结束;
样例输入
2
3
1 1
2 1
1 2
5
2 9 
5 20
11 9
1 1
1 20
样例输出
2
44

求在一条直线上的距离之间之和最短就是求这几个值的中位值。

我们可以从题目中得知y轴上最大值是100,但x没有上限,其实感觉有点奇怪,不过并不影响我们做题。

因为好久没写代码了, 很多注意的地方都没有注意到位。

在写if的时候,多句语段多次忘了括号,导致并没有循环判断累加和清零。同时在测试数据的时候也没考虑到极限的上限,导致了多次没有AC,各种WA

一时间有点心态爆炸xxxxxxxxxxxx

2523945 huayuwenhao 街区最短路径问题 WrongAnswer C/C++ 07-10 17:58:12

2523875

huayuwenhao 街区最短路径问题 WrongAnswer C/C++ 07-10 16:23:40

2523874

huayuwenhao 街区最短路径问题 CompileError C/C++ 07-10 16:22:41

最后还是通过小伙伴们的提醒,用了一组简单的极限数据进行了测试,并且进行了修改

1

10

0 0

0 0

0 0

0 0

0 0

100 100

100 100

100 100

100 100

100 100

很显然结果是1000。多次修改后在这个数据完全没问题之后,跑了一下测试,顺利AC。

2523948 huayuwenhao 街区最短路径问题 Accepted 0 2312 C/C++ 07-10 17:59:55

整体代码如下

#include
int main()
{
int n;
int m;
int i;
int j;
int k=0;
int ans[20];
scanf("%d",&n);
while(k<n)
{
int x[21];
int y[21];
int xmax;
int xsum=0;
int ysum=0;
int sum=0;
int xsummin=0;
int ysummin=0;
scanf("%d",&m);
for (i=1;i<=m;i++)
{
scanf("%d %d",&x[i],&y[i]);
}
xsummin=65000;//注意上限
for (i=1;i<=200;i++)//注意上限
{
for (j=1;j<=m;j++) { if (x[j]>=i)
xsum=xsum+x[j]-i;
else
xsum=xsum+i-x[j];
}
if (xsum<xsummin)//注意多语句段两行括号
{
xsummin=xsum;
xsum=0;
}
}
ysummin=65000;//注意上限
for (i=1;i<=100;i++)
{
for (j=1;j<=m;j++) { if (y[j]>=i)
ysum=ysum+y[j]-i;
else
ysum=ysum+i-y[j];
}
if (ysum<ysummin)//注意多语句段两行括号
{
ysummin=ysum;
ysum=0;
}
}
sum=xsummin+ysummin;
ans[k]=sum;
k=k+1;
}
for(i=0;i<k;i++)
printf("%d\n",ans[i]);
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注