1. 首先，输入数据的第一个数是没用的。
2. 其次，对于第二个数排序。
3. 取出中位数。
4. 计算结果。

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp >> a[i];
    }
    sort(a, a + n);
    int pos = a[n / 2], result = 0;
    for (int i = 0; i < n; i++)
        result += abs(a[i] - pos);
    cout << result << endl;
    return 0;
}

此题为数组的中位数，有几种思路：
（1）最容易想到的当然是使用数组排序，然后最中间的数（或者中间两个的平均值）即为中位数，因为不需要稳定采用快排，时间复杂度为O(nlogn)+O(1)；

（2）第二种也很容易想到，我们只需要求中间的位数，那么即转换为求第n/2个数（对于偶数的数组则求两个），那么我们不必对整个数组进行排序，利用第K最小值的算法即可求出，时间复杂度2 * O(n)；

注：思路在求偶数数组中位数的时候是两个数的平均值，其实依照题意对于偶数数组我们只需取两个的任意一个即可，所以实际上（2）的时间复杂度可以减少为O(n)。

（3）第三种是利用Y值是整数，并且范围为-10000≤x，y≤10000，那我们可以利用桶排序，然后再依次累加则到中位数为止，采用空间换时间的方法来减少计算的代价，最差时间复杂度为O(n)，平均时间复杂度为O(n/2)。

本代码采用了第三种桶排序的方法

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

int bucket[20003];

int main()
{
    //freopen("input.txt", "r", stdin);
    
    int i, j, k;
    int n;
    int x, y;
    //while(scanf("%d", &n) != EOF)
    //{
    scanf("%d", &n);
        memset(bucket, 0, sizeof(bucket));
        for(i = 0; i < n; ++i)
        {
            scanf("%d%d", &x, &y);
            bucket[y + 10000]++;
        }
        
        //求中位数
        int idx1 = (n - 1) / 2;
        int idx2 = n / 2;
        int y1, y2;
        int count = 0;
        for(i = 0; i < 20003; ++i)
        {
            count += bucket[i];
            if(count > idx1) y1 = i;
            if(count > idx2)
            {
                y2 = i;
                break;
            }
        }
        y = (y1 + y2) / 2; //两个数中间的任意数值均可，因此无需求实数的平均数
        
        //求最小距离
        int sum = 0;
        for(i = 0; i < 20003; ++i)
        {
            sum += abs(y - i) * bucket[i];  
        } 
        printf("%d\n", sum);
    //}
    
    //fclose(stdin);
    
    return 0;
}

注意！暴力可以过

#include<bits/stdc++.h>
int main()
{
    int x[10001],y[10001],n;
    scanf("%d",&n);
    long long ans=99999990;
    for(int i=1;i<=n;i++)
      scanf("%d%d",&x[i],&y[i]);
    for(int i=-2500;i<=2500;i++){
        long long sum=0;
        for(int k=1;k<=n;k++){
            sum=sum+fabs(y[k]-i);
        }
        ans=std::min(ans,sum);
    }
    printf("%d",ans);
}

友情提示：读入方式不能freopen
对Y坐标进行排序，选定一个坐标
使其他Y坐标尽可能平均的分布在它的两侧
原理：当油管以上和以下的点数量相等时，
油管不穿过任何点时上下移动，总距离不变
穿过任何的点都会增加距离
所以上下点数量相等时为最短
#include <cstdio>
#include <algorithm>

int abs(int x){
if(x>0)
return x;
else
return -1*x;
}

int main(){
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int n,a[10001],refer,sum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%*d%d",&a[i]);
std::sort(a+1,a+n+1);

if(n%2==0)
refer=a[n/2];
else
refer=a[(n+1)/2];
for(int i=1;i<=n;i++)
sum+=abs(refer-a[i]);
printf("%d",sum);
return 0;
}

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

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

namespace dts
{
    int n,ans,a[10000];
    
    void main()
    {
        scanf("%d",&n);
        for (int i=0,temp;i<n;i++)
            scanf("%d%d",&temp,&a[i]);
        sort(&a[0],&a[n]);
        ans=0;
        for (int i=0,temp=a[n>>1];i<n;i++)
            ans+=(int)abs(a[i]-temp);
        printf("%d\n",ans);
    }
}

int main()
{
    dts::main();
}

到最南和最北的距离之和不变，所以，不断计算差，再求和就行。

#include<iostream>
using namespace std;
int main()
{
    int N, x, y[10000], sum = 0;
    cin >> N;
    for (int i = 0; i < N; i++)cin >> x >> y[i];
    for (int i = 0; i < N - 1; i++)for (int j = i + 1; j < N; j++)if (y[i] > y[j])
    {
        int temp = y[i];
        y[i] = y[j];
        y[j] = temp;
    }
    for (int i = 0; i < N / 2; i++)sum += y[N - i - 1] - y[i];
    cout << sum;
    return 0;
}

#include<stdio.h>
#include<string.h>
#include<math.h>
void qsort(int a[],int l,int r)
{
    int i=l,j=r,mid=a[(l+r)/2],b;
    while(i<=j)
    {
        while(a[i]<mid)i++;
        while(a[j]>mid)j--;
        if(i<=j)
        {
            b=a[i];
            a[i]=a[j];
            a[j]=b;
            i++;
            j--;
        }
    }
    if(l<j)qsort(a,l,j);
    if(r>i)qsort(a,i,r);
} 
int main()
{
    int a[10005]={0},b,i,j,n,sum=0,min=210000000;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    scanf("%d%d",&b,&a[i]); 
    qsort(a,1,n);
    for(i=1;i<=n;i++) 
    {
        for(j=1;j<=n;j++)
        {
            if(a[i]>=a[j])
            sum=sum+(a[i]-a[j]);
            else
            sum=sum-(a[i]-a[j]);
        }
        min=sum;
        sum=0;
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(a[i]>=a[j])
            sum=sum+(a[i]-a[j]);
            else
            sum=sum-(a[i]-a[j]);
        }
        if(sum<=min)
        min=sum;
        sum=0;
    }
    printf("%d",min); 
    return 0;
}

刚开始没看清题。。以为是求费马点，多写了一大堆关于x坐标的代码:)

#include <stdio.h>
#include <stdlib.h>
#ifndef INDEX_I
int index_i=0;
#define INDEX_I
#endif
#define mapTo(data,n,type,function_body)\
    index_i=0;\
    for(;index_i<n;index_i++){\
        type x=data[index_i];\
        type * str_x=&data[index_i];\
        function_body;\
    }
#ifndef RANGE_I
int range_i=0;
#define RANGE_I
#endif
#define for_range(x)\
    range_i=0;\
    for(;range_i<x;range_i++)
#define bigger(x,y) ((x)>(y)?(x):(y))
#define smaller(x,y) ((x)<(y)?(x):(y))
#define abs(x) ((x)<0?(-(x)):(x))
int readInt(){
    int n=0;
    scanf("%d",&n);
    return n;
}
void fillInData(int * data,int n){
    for_range(n) data[range_i]=readInt();
}
int avg(int * data,int n){
    int sum=0;
    mapTo(data,n,int,sum+=x);
    return sum/n;
}
typedef struct{
    int x,y;
} point;
int main(){
    
    int n=readInt();
    point data[10000];
    point point_max,point_min;
    point_max.x=point_max.y=-10001;
    point_min.x=point_min.y=10001;
    //刚开始没读清题，以为是寻找费马点的问题。。。多写了很多无用代码
    for_range(n){
        data[range_i].x=readInt();
        data[range_i].y=readInt();
        point_max.y=bigger(data[range_i].y,point_max.y);
        point_min.y=smaller(data[range_i].y,point_min.y);
    }
    int test_y;
    //玄学，加一个9多AC一条。。
    int smallest_distant=99999999;
    for(test_y=point_min.y;test_y<=point_max.y;test_y++){
        int sum=0;
        mapTo(data,n,point,{
            sum+=abs(x.y-test_y);
        });
        smallest_distant=smaller(sum,smallest_distant);
    }
    printf("%d",smallest_distant);
    return 0;
}

#include<bits/stdc++.h>
int a[100010];
int main() {
    int n, l, ans=0;
    scanf("%d", &n);
    for(int i=1; i<=n; i++) {
        int x;
        scanf("%d%d", &x, &a[i]);
    }
    std::sort(a+1,a+n+1);
    l=n/2;
    for(int i=1; i<=l; i++) ans+=a[n-i+1]-a[i];
    printf("%d", ans);
    return 0;
}

依稀还记得绝对值的几何意义，‘画’数轴秒杀。
#include <iostream>
#include <algorithm>
using namespace std;

int n,temp;
int arr[10005];
int ans=0;

int main() {
cin>>n;
for(int i=1;i<=n;i++){
cin>>temp>>arr[i];
}
sort(arr+1,arr+n+1);
if(n%2==0){
temp=arr[n/2];
for(int i=1;i<n/2;i++){
ans+=temp-arr[i];
}
for(int i=n/2+1;i<=n;i++){
ans+=arr[i]-temp;
}
}else{
temp=arr[n/2+1];
for(int i=1;i<n/2+1;i++){
ans+=temp-arr[i];
}
for(int i=n/2+2;i<=n;i++){
ans+=arr[i]-temp;
}
}
cout<<ans;
return 0;
}

桶排过了

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,y[10000]={0},ans=0,x;
short book[20001]={0},f=0;
void read(int &x)
{
    int f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {read(x);read(y[i]);}
    for(int i=0;i<n;i++)
        book[y[i]+10000]++;
    for(int i=0;i<=20000;i++)
    {
        f+=book[i];
        if(f>n/2)
        {
            x=i-10000;
            break;
        }
    }
    for(int i=0;i<n;i++)
        ans+=abs(y[i]-x);
    cout<<ans;
    return 0;
}

#include <cstdio>
#include <cmath>
#include <algorithm>

int main() {
    int n, a[10001], r = 0, junk;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d %d", &junk, &a[i]);
        
    std::sort(a, a + n);
    int m = a[n / 2];
    for(int i = 0; i < n; i++)
        r += abs(a[i] - m);
    printf("%d", r);
    return 0;
}

用了类似快排的方法，但是只排“一半”，求中位数的期望复杂度为O(n)。（不过这题似乎没必要这样写

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define MAXN 10010

using namespace std;

int x_arr[MAXN], y_arr[MAXN];
int arr[MAXN], n;

int my_rand(int l, int r) {
    srand(rand());
    return (int)rand() % (r - l) + l;
}

void print_arr() {
    for(int i = 0;i < n;++i) {
        printf("%d ", arr[i]);
    }
    putchar('\n');
}

int select_mediate(int l, int r) {
    int pivot = my_rand(l, r);
    // printf("pivot: %d -- %d\n", pivot, arr[pivot]);
    swap(arr[pivot], arr[r-1]);
    // print_arr();
    int i = l, j = l-1;
    for(;i < r;++i) {
        if(arr[i] <= arr[r-1]) {
            swap(arr[++j], arr[i]);
        }
        // printf("i: %d\tj: %d\n", i, j);
        // print_arr();
    }
    if(j < n/2) {
        return select_mediate(j, r);
    }
    else if(j > n / 2) {
        return select_mediate(0, j);
    }
    else {
        if(n % 2 == 1) {
            return arr[j];
        }
        else {
            return (arr[j] + arr[j-1]) / 2;
        }
    }
}

int main() {
    srand(122);
    scanf("%d", &n);
    for(int i = 0;i < n;++i) {
        scanf("%d%d", x_arr+i, y_arr+i);
        arr[i] = y_arr[i];
    }
    int m = select_mediate(0, n);
    int ans = 0;
    for(int i = 0;i < n;++i) {
        ans += abs(y_arr[i] - m);
    }
    printf("%d", ans);
    return 0;
}

这题实际上就是：
求数轴上任意一个数到数轴上给定的n个数距离之和的最小值
不信自己捋捋

不用去重，也是醉了

def sum_abs(m):
    s_rt = 0
    for i_local in range(0, n):
        s_rt += abs(coord_y[i_local] - m)
    return s_rt


n = int(input())

coord_y = []
for i in range(0, n):
    in_put = input().split()
    coord_y.append(int(in_put[1]))
coord_y.sort()
out_put = sum_abs(coord_y[int(n / 2)])
print(out_put)

#include <iostream>
#include <cstdlib>
#include <math.h>
#include <algorithm>
#define MAX 2147483647
using namespace std;

int main()
{
    int n;
    cin>>n;
    int x,y[n];
    for(int i=0;i<n;i++)
        cin>>x>>y[i];
        
    /*暴力枚举
    int ma=-1,mi=MAX;
    for(int i=0;i<n;i++)
    {
        ma=max(ma,y[i]);
        mi=min(mi,y[i]);
    }
    int ans=MAX,temp;
    for(int i=mi;i<=ma;i++)
    {
        temp=0;
        for(int j=0;j<n;j++)
            temp+=abs(y[j]-i);
        ans=min(ans,temp);
    }
    */
    
    //贪心求中位数+快排
    sort(y,y+n);
    int medium=y[n/2];
    int ans=0;
    for(int i=0;i<n;i++)
        ans+=abs(y[i]-medium);
    
    cout<<ans<<endl;
    return 0;
}

//贪心求中位数+桶排序：
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <math.h>
using namespace std;

int main()
{
    int b[20001];
    memset(b,0,sizeof(b));
    int n;
    cin>>n;
    int x,y[n];
    for(int i=0;i<n;i++)
    {
        cin>>x>>y[i];
        b[y[i]+10000]++;
    }
    int temp=0;
    int medium;
    for(int i=0;i<20001;i++)
    {
        temp+=b[i];
        if(temp>n/2)
        {
            medium=i-10000;
            break;
        }
    }
    int ans=0;
    for(int i=0;i<20001;i++)
        ans+=abs(i-10000-medium)*b[i];
    cout<<ans<<endl;
    return 0;
}

n = int(raw_input())
a = [int(raw_input().split()[1]) for i in range(n)]
a = sorted(a)
pos = a[n / 2]
print sum([abs(i - pos) for i in a])

/*Tokgo*/
/*
我们假设一条输油管道的纵坐标为y
此时输油管道上方的油田数量为a
下方的油田数量为b
考虑一下y+1后对长度和L的影响
即L+=a-b;
不难发现，
当管道上下油田数量一样多时
L取最小值
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int x,y[10001];
int L;
int avr;
int len(int a,int b){
    if(a>b) return a-b;
    else return b-a;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>x>>y[i];
    sort(y+1,y+n+1);
    avr=y[(n+1)/2];
    for(int i=1;i<=n;++i)
        L+=len(avr,y[i]);
    cout<<L;
    return 0;
}

绝对值之和的最小值有规律|a|+|b|>=|a+b|，找到规律之后就简单了。但是规律不好找啊
python3
#id1691.py
n = int(input())
lst=[]
for i in range(n):
lst.append( list(map(int,input().split())))
lsty=[]
for i in lst:
lsty.append(i[1])
lsty.sort()#对y值进行排序
if n==1:
result = 0
elif n%2 == 0:
result = abs(sum(lsty[:int(n/2)])-sum(lsty[int(n/2):]))#前半部分之和与后半部分之和的差
else:
result = abs(sum(lsty[:int((n-1)/2)])-sum(lsty[int((n+1)/2):]))#除去中间数之后前半部分与后半部分之差
print(result)