51Nod 1108 距离之和最小 V2 1096 距离之和最小中位数性质-白红宇的个人博客

51Nod 1108 距离之和最小 V2 1096 距离之和最小中位数性质

发布日期：2021-05-09 04:21:30 浏览次数：19 分类：博客文章

本文共 1718 字，大约阅读时间需要 5 分钟。

1108 距离之和最小 V2

基准时间限制：1 秒空间限制：131072 KB 分值: 40 难度：4级算法题收藏关注

三维空间上有N个点, 求一个点使它到这N个点的曼哈顿距离之和最小，输出这个最小的距离之和。

点(x1,y1,z1)到(x2,y2,z2)的曼哈顿距离就是|x1-x2| + |y1-y2| + |z1-z2|。即3维坐标差的绝对值之和。

Input

第1行：点的数量N。(2 <= N <= 10000)

第2 - N + 1行：每行3个整数，中间用空格分隔，表示点的位置。（-10^9 <= X[i], Y[i], Z[i] <= 10^9)

Output

输出最小曼哈顿距离之和。

Input示例

1 1 1

-1 -1 -1

2 2 2

-2 -2 -2

Output示例

思路：

中位数性质：给定一个数列，中位数有这样的性质：所有数与中位数的绝对差之和最小

（转）证明：首先，给定一个从小到大的数列x1,x2,……，xn,设x是从x1到xn与其绝对差之和最小的数，则显然x位于x1与xn之间。那么，由于x1，xn与它们之间的任意一点的距离之和都相等，且都等于xn-x1，因此接下来可以不考虑x1与xn，而考虑剩下的从x2到x[n-1]的数，同样显然有x必然位于x2和x[n-1]之间，依次类推，最后得出的结论是x就是该数列中间的那个数，或者是中间的那两个数之一，而这个数就是中位数。

代码：

1 #include 
     
       2 using namespace std; 3 int x[10001],y[10001],z[10001]; 4 int zws[3]; 5 int cal(int a[], int n) { 6     double num; 7     sort(a,a+n); 8     num=n%2==0?(a[n/2-1]+a[n/2])/2:a[n/2]; 9     return num;10 }11 int main() {12     int n;13     long long dist=0;14     ios::sync_with_stdio(false);15     cin>>n;16     for(int i=0;i
      
       >x[i]>>y[i]>>z[i];18     }19     int xx=cal(x,n);20     int yy=cal(y,n);21     int zz=cal(z,n);22     for(int i=0;i

View Code

1096 距离之和最小

基准时间限制：1 秒空间限制：131072 KB 分值: 20 难度：3级算法题收藏关注

X轴上有N个点，求X轴上一点使它到这N个点的距离之和最小，输出这个最小的距离之和。

Input

第1行：点的数量N。(2 <= N <= 10000)

第2 - N + 1行：点的位置。（-10^9 <= P[i] <= 10^9)

Output

输出最小距离之和

Input示例

-1

-3

Output示例

代码：

1 #include 
     
       2 using namespace std; 3 long long ans[10005]; 4 int main() { 5     int n; 6     long long sum=0; 7     long long num; 8     ios::sync_with_stdio(false); 9     cin>>n;10     for(int i=0;i
      
       >ans[i];12     }13     sort(ans,ans+n);14     if(n%2) num=ans[n/2];15     else num=(ans[n/2]-ans[n/2-1])/2;16     for(int i=0;i

View Code

上一篇：51Nod 1110 距离之和最小 V3 中位数思维

下一篇：HDU 2686 Matrix 多线程dp

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章