张掖做网站免费试用网站制作

给定数轴上的n个点，找出一个到它们的距离之和尽量小的点（即使我们可以选择不是这些点里的点，我们还是选择中位数的那个点最优）
结论:这些点的中位数就是目标点。可以自己枚举推导（很好想）
(对于 点的数量为奇数，是排序之后最中间的数 ，对于点的数量为偶数的情况下，中间两个点 都可以，他俩的答案是相同的，可以简单的画图证明，或者直接抽象一点的想：假设这两个点分别为A B他们之间的距离为d，A相对于B 来说，左侧的点都减少d ，右侧的点都增加d .又因为A左侧的点的个数等于B 右侧的点，所以A B 的值相同)

板子题

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[n>>1]);}cout<<ans<<"\n";
}

添加链接描述

根据上边的引入，可以想到 将数组从中间分成两个子数组。
在考虑一种特殊的情况，就是我两个子数组的中位数相同，这样就不符合题目的要求。
这个时候，两个子数组的中位数肯定有一个要变一下。
有两种可能 左边的中位数-1 / 右边的中位数加1
（为啥左边的中位数不能+1 呢，因为加1 减1 对于数值是原本的中位数的数字 距离是相同的，但是我前边的数大概率有小于我原本中位数的数值，所以我中位数-1 ，距离小的数更进了）

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define int long longvoid solve()
{int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++){cin >> a[i];}sort(a.begin(), a.end());if (n == 2){if (a[0] != a[1]){cout << "0\n";}elsecout << '1' << "\n";return;}int len = n;len /= 2;int pos1 = len / 2;int pos2 = len + len / 2;int ans=0;if (a[pos1] != a[pos2]){//[0 len-1]for (int i=0;i<len;i++){ans+=abs(a[i]-a[pos1]);}for (int i=len;i<n;i++){ans+=abs(a[i]-a[pos2]);}}else{int tar=a[pos2]+1;for (int i=0;i<len;i++){ans+=abs(a[i]-a[pos1]);}for(int i=len;i<n;i++){ans+=abs(a[i]-tar);}int t=0;tar=a[pos1]-1;for (int i=0;i<len;i++){t+=abs(a[i]-tar);}for (int i=len;i<n;i++){t+=abs(a[i]-a[pos2]);}ans=min(ans,t);}cout<<ans<<'\n';
}
signed main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}