【題解】Zerojudge a737 - 10041 - Vito's family

題目連結

題目大意

給定很多位置，請你選擇一個位置使得到其他所有位置距離的和最小，並輸出距離和。

題解

對於一個數列 $a_1 \leq a_2 \leq \dots \leq a_{n - 1} \leq a_n$，$x$ 取數列 $a$ 的中位數使得 $\sum\limits_{i = 1}^n |a_i - x|$ 最小。因此我們只需要將輸入的數列由小到大排序，找出中位數後計算答案即可。

#include <bits/stdc++.h>
using namespace std;

void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	int ans = 0;
	for(int i = 0; i < n; i++) {
		ans += abs(a[i] - a[a.size() / 2]);
	}
	cout << ans << "\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tt;
	cin >> tt;
	while(tt--) {
		solve();
	}
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge a737 - 10041 - Vito's family