首页 > 代码库 > XJOI1564最小距离问题

XJOI1564最小距离问题

最小距离问题

  我国蒙古大草原上有N(N是不大于100的自然数)个牧民定居点P1(X1,Y1)、P2(X2,Y2)、 …Pn(Xn,Yn),相应地有关权重为Wi,现在要求你在大草原上找一点P(Xp,Yp),使P点到任 一点Pi的距离Di与Wi之积之和为最小。   
   即求 D=W1*D1+W2*D2+…+Wi*Di+…+Wn*Dn 有最小值   
   约定距离Di=|Xp-Xi| + | Yp-Yi|

输入格式:

  第一行为正整数N的值   
  第二行至第N+1行,每行有三个数,第一和第二个数分别是这个点的X与Y的坐标,第三个数为它的权重。此三数均为正整数。

输出格式:

第一行是P点坐标X与Y,第二行是最小的D值。 输入与输出数据中一行相邻两个数之间用空格区分。

样例输入:

5
2 4 7
8 11 12
15 8 8
12 80 12
20 60 20

数据范围:

N<=100 XY<=5000
 
如果枚举每一个点,那么最坏要5000*5000*100=2500000000次运算,但是观察题目定义距离,发现x与y是可以分开来计算而互不影响的,于是有了5000*100*2=1000000的正确算法。
 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 const int INF=100000000;
 5 int x[101],y[101],imp[101];
 6 inline int abs(int x){if(x>0)return x;else return -x;}
 7 int main()
 8 {
 9     int n,ax=-INF,ay=-INF,ix=INF,iy=INF;
10     scanf("%d",&n);
11     for(int i=1;i<=n;i++)
12     {
13         scanf("%d%d%d",&x[i],&y[i],&imp[i]);
14         ax=max(ax,x[i]);
15         ix=min(ix,x[i]);
16         ay=max(ay,y[i]);
17         iy=min(iy,y[i]);
18     }
19     int tmp,ans=INF;
20     for(int i=ix;i<=ax;i++)
21     {
22         tmp=0;
23         for(int j=1;j<=n;j++) tmp+=abs(i-x[j])*imp[j];
24         ans=min(ans,tmp);
25     }
26     int a1=ans;
27     ans=INF;
28     for(int i=iy;i<=ay;i++)
29     {
30         tmp=0;
31         for(int j=1;j<=n;j++) tmp+=abs(i-y[j])*imp[j];
32         ans=min(ans,tmp);
33     }
34     ans+=a1;
35     printf("%d",ans);
36     return 0;
37 }

 

XJOI1564最小距离问题