f376 - 芝麻街的團購

🔗 前往 ZeroJudge 原題

題目描述

題目要求找到一個地點，使得所有參與團購的人到該地點的距離總和最小。如果有多個地點可以達到最小距離，則輸出門牌號碼最小的地點。

解題思路

這個問題可以透過找到參與者門牌號碼的中位數來解決。中位數是將所有門牌號碼排序後，位於中間位置的數字。證明如下：假設有 n 個點，x 是最佳的中繼點。如果 x 不是這些點的中位數，那麼我們可以將 x 稍微移動到中位數的位置，總距離會減少。因此，最佳的中繼點一定是中位數。

程式碼首先讀取參與者的人數 n，然後讀取每個人的門牌號碼，並將其儲存在陣列 a 中。接著，使用 sort 函數對陣列 a 進行排序。最後，計算中位數的索引，並輸出對應的門牌號碼。如果 n 是奇數，中位數索引是 n/2。如果 n 是偶數，中位數索引是 n/2 - 1。

複雜度分析

• 時間複雜度: O(n log n)
• 空間複雜度: O(n)

程式碼

#include <iostream>
#include <algorithm>
using namespace std;
int a[100001],n;
int main(){
	cin >> n;
	for(int i=0;i<n;++i)
		cin >> a[i];
	sort(a,a+n);
	cout << a[n/2-(n%2?0:1)];
}