UVA 10041 Vito's Family (中位数)

妖狐艹你老母 2021-12-14 00:29 138阅读 0赞

<table> 
 <tbody> 
  <tr> 
   <td><strong><span style="font-size:24px;color:#c0ffff;">&nbsp;<a rel="nofollow"></a>&nbsp;Problem C: Vito's family&nbsp;</span></strong></td> 
  </tr> 
 </tbody> 
</table>

## Background  ##

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.

## Problem  ##

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)![$s\_1, s\_2, \\ldots, s\_i, \\ldots, s\_r$][s_1_ s_2_ _ldots_ s_i_ _ldots_ s_r] where they live ( 0 < *s**i* < 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  s *i* and  s *j* is  d *ij*= | s *i*\- s *j*|.

## Sample Input  ##

2
    2 2 4 
    3 2 4 6

## Sample Output  ##

2
    4

题意：Vito有r个邻居。。在一条街道上。每个邻居有一个位置。 要求出Vito住的一个地方使得他到所有邻居距离总和最短。

思路：求中位数。。其实也不用求到中位数。。只要把所有邻居从小到大排序，分成两边。取最中间数就可以了。如果是偶数。就两个随便取一个就可以了。。具体原因自己想。

代码：

#include <stdio.h>
    #include <string.h>
    #include <ctype.h>
    #include <algorithm>
    using namespace std;
    
    int t, r, s[505], mid, sum;
    
    int main() {
        scanf("%d", &t);
        while (t --) {
    	sum = 0;
    	scanf("%d", &r);
    	for (int i = 0; i < r; i ++)
    	    scanf("%d", &s[i]);
    	sort(s, s + r);
    	mid = s[r / 2];
    	for (int i = 0; i < r ; i ++) {
    	    sum += abs(s[i] - mid);
    	}
    	printf("%d\n", sum);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/james1207/p/3265432.html

[s_1_ s_2_ _ldots_ s_i_ _ldots_ s_r]: /images/20211213/a06fd7d4f400418ab6a43c7b45a44b6e.png