本文主要是介绍uva 10041 Vito's Family,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
原题:
The world-known gangster Vito Deadstone is moving to New York. He has a very big family there, all of them living in Lamafia Avenue. Since he will visit all his relatives very often, he is trying to find a house close to them. Vito wants to minimize the total distance to all of them and has blackmailed you to write a program that solves his problem.
Input
The input consists of several test cases. The first line contains the number of test cases.
For each test case you will be given the integer number of relatives r (0 < r < 500) and the street
numbers (also integers) s1, s2, … , si , … , sr where they live (0 < si < 30000 ). Note that several
relatives could live in the same street number.
Output
For each test case your program must write the minimal sum of distances from the optimal Vito’s house
to each one of his relatives. The distance between two street numbers si and sj is dij = |si − sj |.
Sample Input
2
2 2 4
3 2 4 6
Sample Output
2
4
中文大意:
在一维数轴上给你一堆点,让你找一个点使得这个点到所有点的距离和最小。输出和即可
#include <bits/stdc++.h>
using namespace std;int main()
{ios::sync_with_stdio(false);int n,t;int a[501];cin>>t;while(t--){cin>>n;memset(a,0,sizeof(a));for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);int ans=0;if(n%2){for(int i=1;i<=n;i++)ans+=abs(a[i]-a[n/2+1]);}else{int tmp=0;for(int i=1;i<=n;i++){ans+=abs(a[i]-a[n/2]);tmp+=abs(a[i]-a[n/2+1]);}ans=min(ans,tmp);}cout<<ans<<endl;}return 0;
}
解答:
超级简单题,找中位数即可。
这篇关于uva 10041 Vito's Family的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!