【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e606
【解題想法】
- 要讓 (|X1 − A| + |X2 − A| + . . . + |Xn − A|) 的值最小，A 是 (X1，X2，…，Xn) 的中位數。
- 先對 a[ ] = (X1，X2，…，Xn) 進行排序，由小排到大。
- 如果 n 是偶數，中位數有兩個， mid1 = a[(n-1)/2] 和 mid2 = a[n/2]
- 如果 n 是奇數，中位數只有一個，mid1 = mid2。
- 【例子】a[ ] = {1, 3, 4, 6, 7, 10}
- 中位數有兩個， mid1 = 4， mid2 = 6。
- A = 4, delta = {3, 1, 0, 2, 3, 6}, sum = 15
- A = 5, delta = {4, 2, 1, 1, 2, 5}, sum = 15
- A = 6, delta = {5, 3, 2, 0, 1, 4}, sum = 15
- 題目要求輸出三個整數:
- 第一個數字是能使該算式最小的最小的 A：mid1
- 第二個數字是|Xi − A|為最小值 (= 0) 的數量：Xi = mid1 or Xi = mid2
- 第三行數字是有幾種可能的 A：mid2 – mid1 + 1
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int main() {
int n;
while (cin >> n){
int a[n];
for (int i = 0; i < n; i++){
cin >> a[i];
}
sort(a, a+n);
int mid1 = a[(n-1)/2];
int mid2 = a[n/2];
int ans = 0;
for (int i = 0; i < n; i++){
if (a[i] == mid1 || a[i] == mid2) ans++;
}
cout << mid1 << " " << ans << " " << mid2 - mid1 + 1 << "\n";
}
return 0;
}