d501 - 第二題：數列最小值
題目描述
題目要求找到一個整數 A，使得數列中所有元素到 A 的絕對差之和最小。如果有多個 A 滿足這個條件，則輸出所有可能的 A 值。
解題思路
這個問題的解法是找到數列的中位數。如果數列長度為奇數，中位數就是唯一解。如果數列長度為偶數，則中位數的兩個值（中間兩個數）都是解。程式碼首先讀取數列長度 n，然後讀取數列中的 n 個元素。接著，使用 sort 函數對數列進行排序。最後，根據數列長度的奇偶性，輸出中位數或中位數的兩個值。對於偶數長度的數列，程式碼會迭代輸出兩個中位數之間的所有整數。
複雜度分析
- 時間複雜度: O(n log n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int a;
while(cin >> a){
cout << "A=";
int b[a];
for(int i=0;i<a;i++){
cin >> b[i];
}
sort(b,b+a);
if(a%2){
cout << b[a/2] << "\n";
}
else{
int c=b[a/2-1],d=b[a/2];
for(;c<=d;c++){
if(c==d){
cout << c << "\n";
}
else{
cout << c << "、";
}
}
}
}
}