日常训练2025-1-21

E双生双宿之错

rating：1300

https://ac.nowcoder.com/acm/contest/95323/E

思路（数论）

本题考查中位数定理，中位数有这样的性质 ：所有数与中位数的绝对差之和最小。中位数是数列中间的那个数，或者是中间的那两个数之一。

所以最后得到的双生数组中的两种数即为数列左半截的中位数，和右半截的中位数。当左右的中位数相同时，让其中一个 +1 或者 -1，特判一下即可

代码

#include <bits/stdc++.h>

typedef std::pair<long long, long long> pll;
typedef std::pair<int, int> pii;
#define INF 0x3f3f3f3f
#define MOD 998244353
using i64 = long long;
const int N = 1e5+5;

void solve(){
	int n;
	std::cin >> n;

	std::vector<int> a(n);
	for (int i = 0; i < n; i++){
		std::cin >> a[i];
	}

	std::sort(a.begin(), a.end());

	int h = n / 2;

	int ml = a[h / 2], mr = a[h + h / 2];

	i64 ans = INF;

	for (auto x : {ml, ml - 1}){
		for (auto y : {mr, mr + 1}){
			if (x == y) continue;

			i64 res = 0;
			for (int i = 0; i < h; i++){
				res += abs(a[i] - x);
			}
			for (int i = h; i < n; i++){
				res += abs(a[i] - y);
			}
			ans = std::min(ans, res);
		}
	}

	std::cout << ans << '\n';
}

signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout<<std::setiosflags(std::ios::fixed)<<std::setprecision(2);
	int t = 1, i;
	std::cin >> t;
	for (i = 0; i < t; i++){
		solve();
	}
	return 0;
}