一维

选取中位数求和

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];

int main(){
    scanf("%d", &n);
    for(int i = 1;i <= n;i ++ ) scanf("%d", &a[i]);
    sort(a + 1, a + 1 + n);
    int ans = 0;
    for(int i = 1;i <= n;i ++ ){
        ans += abs(a[i] - a[1 + n / 2]);
    }

    cout << ans << endl;
    return 0;
}

拓展：二维的欧式距离最短

题目： 星星还是树

第一种：三分套三分

讲解链接：Ternary Search

根据dist = sum(sqrt(dx * dx + dy * dy));
dist 对 x 的二阶偏导大于零 所以是凹函数
三分极小值即可
当 x 固定 dist 对于 y 也是一个凹函数

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

#define INF double(1e10)

using namespace std;

const int N = 150;

int n, x[N], y[N];
double dist = INF;
double eps = 1e-3;
double lx, rx, ly, ry;

double get_dist(double xx, double yy){
    double res = 0;
    for (int i = 1; i <= n; ++i) {
        double dx = x[i] - xx, dy = y[i] - yy;
        res += sqrt(dx * dx + dy * dy);
    }
    return res;
}

double f(double x){
    ly = 0, ry = 10010;
    while(ry - ly > eps){
        double lmid = (ly + ry) / 2;
        double rmid = (lmid + ry) / 2;
        if(get_dist(x, lmid) < get_dist(x, rmid)) ry = rmid;
        else ly = lmid;
    }
    dist = min(dist, get_dist(x, ly));
    return ly;
}

int main() {

    scanf("%d", &n);
    for (int i = 1;i <= n;i ++ ) scanf("%d%d", &x[i], &y[i]);

    lx = 0, rx = 10010;
    while(rx - lx > eps){
        double lmid = (lx + rx) / 2;
        double rmid = (lmid + rx) / 2;
        if(get_dist(lmid, f(lmid)) < get_dist(rmid, f(rmid))) rx = rmid;
        else lx = lmid;
    }

    printf("%.lf\n", dist);

    return 0;
}

第二种：模拟退火

讲解链接：模拟退火

#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>

using namespace std;

const int N = 150;

int n, x[N], y[N];
double ansx, ansy, dist;

double Rand() { return (double)rand() / RAND_MAX; }
double get_dist(double xx, double yy){
    double res = 0;
    for (int i = 1; i <= n; ++i) {
        double dx = x[i] - xx, dy = y[i] - yy;
        res += sqrt(dx * dx + dy * dy);
    }
    // if(res < dist) dist = res, ansx = xx, ansy = yy;
    return res;
}

void simulateAnneal(){
    double T = 1e5; // 初始温度要足够大
    double eps = 1e-6; // 结束温度足够低
    double down = 0.99; // 降温时间足够长
    double nowx = ansx, nowy = ansy;
    while(T > eps){
        // 随机 计算数值
        double nxtx = nowx + T * (Rand() * 2 - 1);
        double nxty = nowy + T * (Rand() * 2 - 1);
        double delta = get_dist(nxtx, nxty) - get_dist(nowx, nowy);
        if(delta < 0) nowx = nxtx, nowy = nxty, dist = dist + delta;
        T *= down;
    }

    ansx = nowx, ansy = nowy;
    for (int i = 1; i <= 1000; ++i) {
        double nxtx = ansx + T * (Rand() * 2 - 1);
        double nxty = ansy + T * (Rand() * 2 - 1);
        double z = get_dist(nxtx, nxty);
        if(z < dist) dist = z, ansx = nxtx, ansy = nxty;
    }
}
int main() {

    srand(time(0));
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &x[i], &y[i]);
        ansx += x[i], ansy += y[i];
    }
    // 初始化 初解
    ansx /= n, ansy /= n, dist = get_dist(ansx, ansy);
    // 模拟退火
    simulateAnneal();
    // printf("%.3lf %.3lf\n", ansx, ansy);
    printf("%.lf\n", get_dist(ansx, ansy));

    return 0;
}