Question

一道ACM题 求代码！！做出者有奖！！！！！！！！

设平面上一共有N个整数点(xi,yi)(0< =i< N),现在从中任选出M(M< =N)个点，再从中任意选择一个点(x,y)，你能计算出点(x,y)和这M个点距离之和的最小值吗?
其中，点(x,y)和点(xi,yi)之间的距离定义为：|x-xi|+|y-yi|

Input首先输入一个数cas，代表下面共有cas组测试数据。
对于每组数据首先输入数N，M，(1< =N< =100)。代表共有N个点，并选择其中的M个。然后接下来N行，依次输入这N个点的坐标(xi,yi)(0< =i< N)。

Output输出距离和的最小值，输出一组后换行输出另一组。(所有结果都在int范围内)
Sample Input
2
3 2
1 0
10 0
12 0

3 2
1 1
2 2
4 4
Sample Output
2
2

Answer 1

//枚举选择的点，将剩余的点到它的距离排序后求和即可，复杂度n^2log(n)
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=105;
struct point{
int x,y;
void input(){ scanf("%d%d",&x,&y);}
}list[105];
int n,m;
int dist(point a,point b){
return abs(a.x-b.x)+abs(a.y-b.y);
}
void solve(){
int d[maxn],ct,ans=0x7f7f7f7f;
for(int i=0;i<n;i++){//依次枚举中心点
ct=0;
int tmp=0;
for(int j=0;j<n;j++){//计算中心点到其他点的距离
if(j==i) continue;
d[ct++]=dist(list[i],list[j]);
}
sort(d,d+ct);//排序
for(int j=0;j<m-1;j++) tmp+=d[j];//求和,除去自身所以取m-1个
ans=min(ans,tmp);//更新
}
printf("%d\n",ans);
}
int main(){
int ca;
scanf("%d",&ca);
while(ca--){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) list[i].input();
solve();
}
return 0;
}

Answer 2

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
main()
{
int x[103],y[103],i,j,k,dd[103],d[103],n,m,t,cas,min;
while(scanf("%d",&cas)!=EOF)
{
while(cas--)
{
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
scanf("%d%d",&x[i],&y[i]);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)

dd[j]=abs(x[i]-x[j])+abs(y[i]-y[j]);

for(j=0;j<n-1;j++)
for(k=j+1;k<n;k++)
if(dd[j]>dd[k])
{
t=dd[j];dd[j]=dd[k];dd[k]=t;
}
d[i]=0;
for(j=0;j<m;j++)
d[i]+=dd[j];
}
min=d[0];
for(i=1;i<n;i++)
if(d[i]<min)
min=d[i];
printf("%d\n",min);

}
}
}