BISHI25　最大 FST 距离¶

中等通过率 31.79%python3样例通过牛客 AC排序

牛客原题　源码

讲解章节：自定义排序、排序

一句话

求 max(|i^2 - j^2| + |A_i^2 - A_j^2|)。

解题思路¶

这题考什么¶

换个视角把式子看成几何量。令 x_i = i^2、y_i = A_i^2，要求的就是平面点集上最大的曼哈顿距离 max(|x_i - x_j| + |y_i - y_j|)。

曼哈顿距离有一条常用恒等式：拆掉两层绝对值只有四种符号组合，取其最大者

|dx| + |dy| = max( (x_i + y_i) - (x_j + y_j), (x_j + y_j) - (x_i + y_i),
                   (x_i - y_i) - (x_j - y_j), (x_j - y_j) - (x_i - y_i) )

也就是说，每个点只需记住两个标量 u = x + y 和 v = x - y，答案就是

max( max(u) - min(u), max(v) - min(v) )。

这一步把「枚举点对」换成了「对两个一维数组各取一次最值」。

数据规模与复杂度¶

n <= 1e5。两两枚举有 n*(n-1)/2 ≈ 5e9 对，必然超时；本做法只扫一遍构造 u、v，再各取最值，O(n) 时间、O(n) 空间。 A_i <= 1e9 使 A_i^2 <= 1e18，两项相加接近 2e18，C/C++ 用 long long 刚好够但很贴边；Python 是任意精度整数，无溢出之忧。

坑在哪¶

下标 i 是 1-based。样例 n=2、A=[4,3] 的答案用的是 2^2 - 1^2 = 3，若按 0-based 算成 1^2 - 0^2 = 1，结果会输出 8 而不是 10。代码里循环写 range(1, n + 1)、取值写 a[i - 1]，就是为了对齐这个偏移。
n = 1 时不存在任何点对，答案应为 0。此时 sp、sm 各只有一个元素，最大值与最小值相同，公式天然给出 0，不必特判。
必须先平方再作差，|i - j| + |A_i - A_j| 与题目定义的不是同一个量。
u 和 v 两组都要算。两点的相对位置（连线斜率的正负）决定了最大值出现在哪一组，只算其中一组会漏掉另一半情况。

样例复核¶

n=2, A=[4,3]：点 1 是 (x, y) = (1^2, 4^2) = (1, 16)，点 2 是 (2^2, 3^2) = (4, 9)。 u = 17 与 13，极差 4；v = -15 与 -5，极差 10。取较大者 10，与样例说明里的 |4^2-3^2| + |2^2-1^2| = 7 + 3 = 10 一致。

参考实现¶

solutions/BISHI25.py
import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
a = data[1:n + 1]

sp = []   # x + y
sm = []   # x - y
for i in range(1, n + 1):
    x = i * i               # 下标 1-based，直接用循环变量 i 平方
    y = int(a[i - 1]) ** 2  # token 列表是 0-based，故取 i-1
    sp.append(x + y)
    sm.append(x - y)

# 曼哈顿距离最大值 = 两组标量各自极差中的较大者
print(max(max(sp) - min(sp), max(sm) - min(sm)))

BISHI25 最大 FST 距离¶