d452 - 二、直線最小距離和

🔗 前往 ZeroJudge 原題

題目描述

題目要求找出數線上一個點，使得該點到給定數線上所有點的距離和最小。

解題思路

這個問題可以透過排序和貪心算法來解決。核心思想是，數線上所有點的距離和最小的位置一定是數線上所有點的中位數。因此，首先對給定的點的座標進行排序，然後選擇排序後數組的中間元素作為最佳位置。由於題目沒有明確說明 m 是奇數還是偶數，但中位數的概念對於奇數和偶數的數組都適用。對於偶數個點，可以選擇中間兩個數的其中一個作為中位數，因為這兩個數的距離和是最小的。程式碼中直接選擇 a[m/2] 作為中位數。然後，計算該點到所有其他點的距離和，即為最小距離和。

複雜度分析

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

程式碼

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	int N,m,k;
	cin >> N;
	while(N--){
		cin >>  m;
		int a[m],ans=0,k=m/2;
		for(int i=0;i<m;i++){
			cin >> a[i];
		}
		sort(a,a+m);
		for(int i=0;i<m;i++){
			ans+=abs(a[i]-a[m/2]);
		}
		cout << ans << "\n";
	}
}