2972.
MOVING DHAKA
Time Limit: 2.0 Seconds
Memory Limit: 65536K
Total Runs: 344
Accepted Runs: 97
I am moving to Dhaka. I have many friends there. Since I shall visit all my friends very often, I am trying to find a house close to them. I want to minimize the total distance to all of them and have blackmailed you to write a program that solves my problem.
Input
The input consists of several test cases. For each test case you will be given the integer number of friends r ( 0 < r < 1000000) and the street numbers (also integers) where they live ( 0 < si < 2000000000 ). 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 my 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
Problem Setter: Md. Shakil Ahmed.
Source: CUET Easy Contest
Submit
List Runs Forum Statistics
#include
<
iostream
>
#include
<
cmath
>
#include
<
algorithm
>
#define
MAX 1000002
using
namespace
std;
int
t,n;
int
data[MAX];
bool
comp(
int
a,
int
b) {
return
a
<
b; }
int
main() { scanf(
"
%d
"
,
&
t);
while
(t
--
) {
int
i; scanf(
"
%d
"
,
&
n);
for
(i
=
1
;i
<=
n;i
++
) scanf(
"
%d
"
,
&
data[i]); sort(data
+
1
,data
+
n
+
1
,comp);
long
long
sum
=
0
;
int
mid
=
(n
+
1
)
/
2
;
for
(i
=
1
;i
<=
n;i
++
) { sum
+=
abs(data[i]
-
data[mid]); } printf(
"
%lld\n
"
,sum); }
return
0
; }
转载于:https://www.cnblogs.com/forever4444/archive/2009/05/19/1460376.html
