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"; } }
|