CPE 一顆星選集 49 道必考題
題目連結:https://zerojudge.tw/ShowProblem?problemid=a737
內容
給定一數列，求一數使其到每個數之距離和為最小，輸出最小距離和。
輸入的第一列有一個整數代表以下有多少組測試資料。
每組測資一列，第一個整數 r (0 < r < 500)代表數列長度，接下來的 r 個整數s1,s2,……sr為數列值（0 < si <30000）。
範例輸入
3
2 2 4
3 2 4 6
4 2 1 999 5
範例輸出
2
4
1001
想法
排序後取中位數，再掃一遍已排序數列找距離。
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;
int main(){
fastio;
int T, n, mp[500], sum, mid;
cin >> T;
while(T--){
cin >> n;
for(int i = 0; i < n; ++i) cin >> mp[i];
sort(mp, mp + n);
sum = 0;
if(n & 1) mid = mp[n >> 1];
else mid = (mp[n >> 1] + mp[(n >> 1) - 1]) >> 1;
for(int i = 0; i < n; ++i){
sum += abs(mp[i] - mid);
}
cout << sum << "\n";
}
}
|