e606 - 10057 - A mid-summer nights dream
題目描述
題目要求找出一個整數 A，使得 |X1 - A| + |X2 - A| + ... + |Xn - A| 的值最小，並輸出這個 A 值、最小值出現的次數，以及可能的最小值個數。
解題思路
這個問題可以透過找到數列的中位數來解決。當 n 為奇數時，中位數就是能使上述式子最小化的 A 值。當 n 為偶數時，任何位於兩個中間數之間的 A 值都能使上述式子最小化，因此我們選擇較小的中間數作為 A 值。 程式碼首先讀取輸入的數字 n 和數列中的元素，然後對數列進行排序。接著，根據 n 的奇偶性計算 A 值和最小值出現的次數。對於偶數的情況，還需要計算可能的最小值個數，即兩個中間數之間的範圍大小加 1。
複雜度分析
- 時間複雜度: O(n log n) (主要來自排序)
- 空間複雜度: O(n) (用於儲存輸入數列)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n;
while(cin >> n){
int a[n];
for(int i=0;i<n;i++)
cin >> a[i];
sort(a,a+n);
if(n&1){
int mid=a[n/2],t=0;
cout << mid << " ";
for(int i=0;i<n;i++)
if(a[i]==mid)
t++;
cout << t << " 1\n";
}
else{
int mid1=a[n/2],mid2=a[n/2-1],t=0;
cout << mid2 << " ";
for(int i=0;i<n;i++)
if(a[i]==mid1||a[i]==mid2)
t++;
cout << t << " " << mid1-mid2+1 << "\n";
}
}
}