您的位置: 首页 > 文章 > house 题解 house 题解 分类: 文章 • 2024-05-29 11:35:34 househousehouse 题解 题目 解题方法 我们可以发现第iii和第jjj的的房子的距离是li+lj+∣pi−pj∣l_i+l_j+|p_i-p_j|li+lj+∣pi−pj∣。 对于上面有绝对值的式子，我们可以先把lll排序，就可以把绝对值去掉，得li+lj+pi−pjl_i+l_j+p_i-p_jli+lj+pi−pj。 我们可以把下标为iii合并，下标为jjj的合并，得li+pi+(lj−pj)l_i+p_i+(l_j-p_j)li+pi+(lj−pj)。 那么就可以用一个变量维护lj−pjl_j-p_jlj−pj，然后每一次用这个变量加上li+pil_i+p_ili+pi，求一次最大值就行了。时间复杂度为排序复杂度，O(nlog2n)O(n\log_{2}^{n})O(nlog2n)。
