2025牛客WC1-E-双生双宿之错 · znzryb
## 思路讲解
参考题解：
[https://ac.nowcoder.com/discuss/1452661](https://ac.nowcoder.com/discuss/1452661)
[https://ac.nowcoder.com/discuss/1452662](https://ac.nowcoder.com/discuss/1452662)（这个题解好）
[](https://www.notion.so/1354539447bd80259ef5fcf83280fa35)
中位数定理，其实类似于树的重心（以该点为根，最大子树最小），都是不能牺牲大我
只有一个点左边也有n个点，右边也有n个点，到达该点距离之和最短
其实数轴就是一种特殊的树嘛～～
## AC代码
AC [https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74961575](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74961575)
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(1e5)+10;
ll N,T,A[MAXN];
void solve() {
cin>>N;
for(int i=1;i<=N;++i) {
cin>>A[i];
}
sort(&A[1],&A[N+1]);
// 中位数定理
ll mid1,mid2;
if(N%4==0) mid1=A[N/4]+A[N/4+1]>>1,mid2=A[3*N/4]+A[3*N/4+1]>>1;
else mid1=A[N/4+1],mid2=A[3*N/4+1]; // 是不是严格在中间是不重要的
if(mid1==mid2) {
mid1-=1; // 强制-1（6 6 6 6那个数据）
ll dis=0,dis2=0;
for(int i=1;i<=N;++i) {
if(i<=N/2) {
dis+=abs(A[i]-mid1);
}else {
dis+=abs(A[i]-mid2);
}
}
mid1+=1,mid2+=1;
for(int i=1;i<=N;++i) {
if(i<=N/2) {
dis2+=abs(A[i]-mid1);
}else {
dis2+=abs(A[i]-mid2);
}
}
cout<<min(dis,dis2)<<'\n';
return;
}
ll dis=0;
for(int i=1;i<=N;++i) {
if(i<=N/2) {
dis+=abs(A[i]-mid1);
}else {
dis+=abs(A[i]-mid2);
}
}
cout<<dis<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while (T--) {
solve();
}
return 0;
}
/*
3
4
1 1 3 1
4
6 6 6 6
6
1 1 4 4 1 4
*/
```
## 心路历程（WA，TLE，MLE……）
[](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74959849)
前面一直有点问题，结果是因为这个特判mid1-=1和mid2+=1都要算
```cpp
if(mid1==mid2) {
mid1-=1; // 强制-1（6 6 6 6那个数据）
ll dis=0,dis2=0;
for(int i=1;i<=N;++i) {
if(i<=N/2) {
dis+=abs(A[i]-mid1);
}else {
dis+=abs(A[i]-mid2);
}
}
mid1+=1,mid2+=1;
for(int i=1;i<=N;++i) {
if(i<=N/2) {
dis2+=abs(A[i]-mid1);
}else {
dis2+=abs(A[i]-mid2);
}
}
cout<<min(dis,dis2)<<'\n';
return;
}
```