题解：B4568 [山东省小学组体验营 2026] 中位数

yanghechen · 2026-08-04 15:06:11 · 题解

贪心。

容易注意到比中位数小的元素都对中位数没有影响，于是让较小的数全都减去较大值，并对剩余数排序并从小到大对应从小到大的减数，找最小值即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,ans=0x7fffffff,a[100100];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    int sz=(n-1)/2;
    for(int i=sz+1;i<=n;i++)
    {
        if(a[i]-(i-sz)<ans)ans=a[i]-(i-sz);
    }
    cout<<ans;
    return 0;
}