题目连接：http://acm./problem/4043
博客园食用链接： /lonely-wind-/p/13941890.html
Description
众所周知，石上同学由于沉迷游戏，导致成绩惨淡，要是这次考试再不及格，他就要留级了，由于这次考前接受过四宫前辈的教导，如果再不及格，石上一定会死的很惨(因为四宫前辈太恐怖了)，于是石上通宵刷题，但是他被一道简单题卡住了，于是他向你求助（因为四宫前辈太可怕，不敢去问），希望你能帮帮他。
这道题是这样的：在一个三维空间上，有 nnn 个点，每个点的坐标用 (xi,yi,zi)(x_i, y_i, z_i)(xi,yi,zi) 表示， 现在需要你找到一个点 (x,y,z)(x, y, z)(x,y,z) ，使得其他 nnn 个点到这个点的曼哈顿距离最小。
两个点 i,ji, ji,j 之间的曼哈顿距离 disdisdis 定义为：dis=∣xi−xj∣+∣yi−yj∣+∣zi−zj∣dis = |x_i - x_j| + |y_i - y_j| + |z_i - z_j|dis=∣xi−xj∣+∣yi−yj∣+∣zi−zj∣
∣a−b∣|a - b|∣a−b∣ 表示 aaa 和 bbb 的差值的绝对值
input
第一行一个整数 nnn , (1≤n≤1e5)(1 \leq n \leq 1e5)(1≤n≤1e5)
接下来有 nnn 行，每行 333 个数 x,y,zx, y, zx,y,z ，代表第 iii 个数的坐标， (−1e9≤x,y,z≤1e9)(-1e9 \leq x,y,z \leq 1e9)(−1e9≤x,y,z≤1e9)
output
输出一个整数，表示答案
Sample Input 1
3
-5 -10 -9
-2 7 2
-9 5 -4
Sample Output 1
35
Sample Input 2
2
-3 2 -2
-2 -5 -5
Sample Output 2
11
emmm，看一下要求的，假设我们找到的点为P那么答案就是：ans=min(∑i=1n∣xp−xi∣+∣yp−yi∣+∣zp−zi∣)ans=min(\sum_{i=1}^{n}|x_p-x_i|+|y_p-y_i|+|z_p-z_i|)ans=min(∑i=1n∣xp−xi∣+∣yp−yi∣+∣zp−zi∣)，那么由于都是取绝对值的，所以我们可以直接化为ans=min(∑i=1n∣xp−xi∣)+min(∑∣yp−yi∣)+min(∑zp−zi)ans=min(\sum_{i=1}^{n}|x_p-x_i|)+min(\sum|y_p-y_i|)+min(\sum z_p-z_i)ans=min(∑i=1n∣xp−xi∣)+min(∑∣yp−yi∣)+min(∑zp−zi)，也就是我们只需要解决一个问题就好了，也就是解决求解min(∑xp−xi)min(\sum x_p-x_i)min(∑xp−xi)，很明显这个结果在一维坐标轴上从左到右他是一个先降后增的。也就是一个二次函数抛物线形的，那么也就可以直接三分求解xpx_pxp了，其他的同理可得。
以下是AC代码：
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int mac=1e5+10;const int inf=1e9+10;int x[mac],y[mac],z[mac];int n;ll cal(ll x,int *a){ll ans=0;for (int i=1; i<=n; i++)ans+=abs(x-a[i]);return ans;}ll solve(int *a) {ll l = -inf, r = inf;while(l < r) {ll x1 = floor(1.0 * (2ll * l + r) / 3);ll x2 = floor(1.0 * (l + 2ll * r + 2) / 3);if(cal(x1,a) < cal(x2,a)) r = x2 - 1;else l = x1 + 1;}return r;}int main(int argc, char const *argv[]){scanf ("%d",&n);for (int i=1; i<=n; i++)scanf ("%d%d%d",&x[i],&y[i],&z[i]);ll xp=solve(x);ll yp=solve(y);ll zp=solve(z);ll ans=0;for (int i=1; i<=n; i++)ans+=(abs(xp-x[i])+abs(yp-y[i])+abs(zp-z[i]));printf("%lld\n",ans);return 0;}
当然实际上用不着这么麻烦，实际上有个结论，我们直接取每个坐标的中位数就行了。
以下是AC代码：
#include <bits/stdc++.h>using namespace std;#define srt(x) sort(x,x+n)const int mac=1e5+10;typedef long long ll;ll x[mac],y[mac],z[mac];int main(int argc, char const *argv[]){int n;scanf ("%d",&n);for (int i=0; i<n; i++)scanf ("%lld%lld%lld",&x[i],&y[i],&z[i]);srt(x);srt(y);srt(z);ll ans=0;for (int i=0; i<n; i++)ans+=abs(x[n/2]-x[i])+abs(y[n/2]-y[i])+abs(z[n/2]-z[i]);printf("%lld\n",ans);return 0;}
如果觉得《CSUSTOJ-石上优不想留级（一维坐标三分及思维解法）》对你有帮助，请点赞、收藏，并留下你的观点哦！
