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

XJOI1564最小距离问题

2024-09-02 19:51:28   218人阅读

最小距离问题

　　我国蒙古大草原上有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最小距离问题


联系
我们