• 欢迎光临~

Codeforces 823B

开发技术 开发技术 2022-10-22 次浏览

题意:

对若干正整数二元组((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越靠近最优结果,lr肯定越靠近一个值)。

官方题解和个人感悟:

​ 考虑当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个点时,类似,不过此时应该是向右移动。

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

程序员灯塔
转载请注明原文链接:Codeforces 823B
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com