题目链接：https://www.luogu.com.cn/problem/U362860

最短过题代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int maxn = 1111111;
int n,a[maxn],median_a;
//a数组 只用来存纵坐标

signed main(){
	cin >> n;
	for ( int i=1; i<=n; i++ ){
		int xx,yy; cin >> xx >> yy;
		a[i] = yy;
	}
	
	sort(a+1,a+1+n);
	median_a = (a[n/2+1]);
	
	int ans = 0;
	for ( int i=1; i<=n; i++ )
		ans += abs( a[i]-median_a );
	cout << ans;
}

手写归并排序：

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int maxn = 1111111;
int n,a[maxn],median_a;
//a数组 只用来存纵坐标

int tmpa[maxn];
void msort( int l, int r ){
  if ( l>=r ) return;
  
  int mid = (l+r)/2;
  msort(l,mid);
  msort(mid+1,r);
  
  int p1=l, p2=mid+1, p3=l;
  while ( p1<=mid && p2<=r ){
  	//按照升序归并进tmpa
  	if ( a[p1] <= a[p2] )
  		tmpa[p3++] = a[p1++];
  	else
  		tmpa[p3++] = a[p2++];
  }
  //如果还剩一个数组没归并完，直接把剩下的copy进tmpa
  while ( p1<=mid )
  	tmpa[p3++] = a[p1++];
  
  while ( p2<=r )
  	tmpa[p3++] = a[p2++];
  
  //再copy回a
  for ( int i=l; i<=r; i++ )
  	a[i] = tmpa[i];
}

signed main(){
  cin >> n;
  for ( int i=1; i<=n; i++ ){
  	int xx,yy; cin >> xx >> yy;
  	a[i] = yy;
  }
  
  msort(1,n);
  median_a = (a[n/2+1]);
  
  // cout << "[debug] median for this case: " << median_a << '\n';
  
  int ans = 0;
  for ( int i=1; i<=n; i++ )
  	ans += abs( a[i]-median_a );
  cout << ans;
}

快速选择：（会TLE）

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int maxn = 1111111;
int n,a[maxn],median_a;
//a数组 只用来存纵坐标

int qselect(int l, int r, int k){
  if ( !(k>=l && k<=r) ){
  	cout << "[error] Invalid Range of k.\n";
  	return -1;
  }
  	
  if ( l==r )
  	return a[l];
  
  int& pivotNum = a[r];
  int i = l-1;
  for ( int j=l; j<=r-1; j++ ){
  	if ( a[j] <= pivotNum ){
  		i++;
  		swap(a[i], a[j]);
  	}
  }
  
  i++;
  swap(a[i], a[r]);
  
  int pivotIdx = i;
//	cout << "[debug]pivotIdx: " << pivotIdx << '\n';
  
  if ( k==pivotIdx )
  	return a[k];
  else if ( k<pivotIdx )
  	return qselect( l, pivotIdx-1, k );
  else 
  	return qselect( pivotIdx+1, r, k );
  
}

signed main(){
  cin >> n;
  for ( int i=1; i<=n; i++ ){
  	int xx,yy; cin >> xx >> yy;
  	a[i] = yy;
  }
  
  median_a = qselect(1, n, n/2+1);
  
  int ans = 0;
  for ( int i=1; i<=n; i++ ){
  	ans += abs(a[i]-median_a);
  }
  cout << ans;
  
}

还有 我真的很不理解 为什么实验报告要求一定要用分治