中位数定理：小试牛刀＞ _ ＜2025牛客寒假1

给定数轴上的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 long

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());
    if (n == 2)
    {
        if (a[0] != a[1])
        {
            cout << "0\n";
        }
        else
            cout << '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;
}