Codeforces 823B

题意：

对若干正整数二元组\((x_i,t_i)\)，求一个实数\(x_0\)，使得\(max\{ t_i+|x_i-x_0|\}\)最小。n<=1e5。

思考：

​ 虽然问的是\(x_0\)，但不妨对这个最小的最大值进行二分，也就是——对于当前mid，是否存在\(x_0\)使得任意\(t_i+|x_i-x_0|<=mid\)。对每个i对应的不等式，解得\(x_i+(mid-t_i)<=x_0<=x_i-(mid-t_i)\)，记为\(l<=x_0<=r\)。如果\(x_0\)存在，那它便需要满足所有的不等式，我们把约束条件合并，得到\(l_{max}<=r_{min}\)。最后一次二分的\(l_{max}\)或\(r_{min}\)（反正相差足够小）就是我们想要的解（因为随着mid越靠近最优结果，l和r肯定越靠近一个值）。

官方题解和个人感悟：

​ 考虑当t均为0时，问题转换到坐标轴上，很显然无论\(x_0\)位于何处，离它最远的点要么是最左点，要么是最右点，我们取中心即可。当引入\(t_i\)后，我们便又多了一维坐标轴（表示\(t_i\)的值），所问距离也变成了平面上的曼哈顿距离，然后依旧是在原坐标轴上寻找\(x0\)。

​ 对于二元组\((x_i,t_i)\)，我们可以考虑将\(t_i\)“扳”回到原坐标轴上。比如当\(x_0\)在\(x_i\)左边时，\(t_i\)应“扳”向右边，也就是把\(x_i\)向右移动\(t_i\)从而向上一段的特殊情况转换。如果“扳”向左边，那么其对结果的贡献显然会被“扳”向右边的值给隐匿掉（因为绝不会比“扳”向右边更优）。

也就是说，若一个个体在假定不同的解时有不同的状态，我们可以尝试将拆它所有状态拆分出来使之独立，满足这些状态最后只有一个会作出贡献，其余的会被隐匿掉。

如此一来，将所有二元组转换为\(x_i+t_i\)和\(x_i-t_i\)，取最大值和最小值的平均值，即解。

相关问题：

对若干整数\(x_i\)，求一个实数\(x_0\)，使得\(\sum |x_i-x_0|\)最小。

结论：最优的解就是这些数的中位数

证明：

​ 想象一数轴，任意找一个点，它左边有4个点，右边有2个点，把该点往左移动一点点，不要移动太多，以免碰到其他输入点。假设移动了d单位距离，则该点到左边4个点的距离各减少d，该点都右边2个点的距离各增加d,但总的来说，距离之和减少了2d。

​ 同理，该点的左边有2个点，右边有4个点时，类似，不过此时应该是向右移动。

​ 换句话说，只要该点的左右两边的输入点个数不一样多，就不是最优解。那什么情况下，左右点一样多呢？如果输入点有奇数个，则最优解应该是中间那个点即中位数。如果有偶数个，则可以位于最中间两个点的任意位置（还是中位数）。