一维
选取中位数求和
#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;
}