北京 营销型网站,连云港seo公司,一般哪些商家需要建设网站,西部数码网站工具给定数轴上的n个点#xff0c;找出一个到它们的距离之和尽量小的点#xff08;即使我们可以选择不是这些点里的点#xff0c;我们还是选择中位数的那个点最优#xff09; 结论:这些点的中位数就是目标点。可以自己枚举推导#xff08;很好想#xff09; (对于 点的数量为…给定数轴上的n个点找出一个到它们的距离之和尽量小的点即使我们可以选择不是这些点里的点我们还是选择中位数的那个点最优 结论:这些点的中位数就是目标点。可以自己枚举推导很好想 (对于 点的数量为奇数是排序之后最中间的数 对于点的数量为偶数的情况下中间两个点 都可以他俩的答案是相同的可以简单的画图证明或者直接抽象一点的想假设这两个点分别为A B他们之间的距离为dA相对于B 来说左侧的点都减少d 右侧的点都增加d .又因为A左侧的点的个数等于B 右侧的点所以A B 的值相同)
板子题
void solve()
{int n;cinn;vectorinta(n);for (int i0;in;i){cina[i];}sort(a.begin(),a.end());int ans0;for (int i 0;in;i){ansabs(a[i]-a[n1]);}coutans\n;
}添加链接描述 根据上边的引入可以想到 将数组从中间分成两个子数组。 在考虑一种特殊的情况就是我两个子数组的中位数相同这样就不符合题目的要求。 这个时候两个子数组的中位数肯定有一个要变一下。 有两种可能 左边的中位数-1 / 右边的中位数加1 为啥左边的中位数不能1 呢因为加1 减1 对于数值是原本的中位数的数字 距离是相同的但是我前边的数大概率有小于我原本中位数的数值所以我中位数-1 距离小的数更进了
#include bits/stdc.h
using namespace std;
typedef pairint, int PII;
#define int long longvoid solve()
{int n;cin n;vectorint 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 ans0;if (a[pos1] ! a[pos2]){//[0 len-1]for (int i0;ilen;i){ansabs(a[i]-a[pos1]);}for (int ilen;in;i){ansabs(a[i]-a[pos2]);}}else{int tara[pos2]1;for (int i0;ilen;i){ansabs(a[i]-a[pos1]);}for(int ilen;in;i){ansabs(a[i]-tar);}int t0;tara[pos1]-1;for (int i0;ilen;i){tabs(a[i]-tar);}for (int ilen;in;i){tabs(a[i]-a[pos2]);}ansmin(ans,t);}coutans\n;
}
signed main()
{std::cin.tie(nullptr)-sync_with_stdio(false);int t 1;cin t;while (t--){solve();}return 0;
}
