题解 | #最大 FST 距离#

题目链接

题目描述

给定 $n$ 个元素，第 $i$ 个元素具有特征值 $p_i$ (其中 $i$ 从 1 到 $n$ ）。定义两个元素 $i$ 和 $j$ 之间的 FST 距离为： $FST(i, j) = |p_i^2 - p_j^2| + |i^2 - j^2|$ 。请计算在所有可能的元素对中，最大的FST距离。

解题思路

本题要求解所有元素对之间FST距离的最大值。一个直接的暴力解法是使用两层循环，遍历所有下标对 $(i, j)$ 并计算距离，但其时间复杂度为 $\mathcal{O}(n^2)$ ，对于 $n$ 较大的情况会超时。我们需要通过数学变换来优化。

核心思想：曼哈顿距离的转换

识别模型：仔细观察FST距离的公式 $FST(i, j) = |p_i^2 - p_j^2| + |i^2 - j^2|$ 。如果我们把每个元素 $i$ 看作一个二维平面上的点，其坐标为 $(x_i, y_i)$ ，其中 $x_i = p_i^2$ ， $y_i = i^2$ 。那么，FST距离的公式恰好是两个点 $(x_i, y_i)$ 和 $(x_j, y_j)$ 之间的曼哈顿距离（也称L1距离）。
公式转换：曼哈顿距离有一个重要的性质，可以将其转换为切比雪夫距离（L∞距离）相关的问题。对于任意两点 $(a, b)$ 和 $(c, d)$ ，它们的曼哈顿距离为： $|a - c| + |b - d| = \max(|(a+b) - (c+d)|, |(a-b) - (c-d)|)$

将这个恒等式应用到我们的问题中，令 $a=x_i, b=y_i, c=x_j, d=y_j$ ： $FST(i, j) = \max(|(x_i+y_i) - (x_j+y_j)|, |(x_i-y_i) - (x_j-y_j)|)$
问题简化：现在，我们定义两个新的序列 $U$ 和 $V$ ：
- $U_k = x_k + y_k = p_k^2 + k^2$
- $V_k = x_k - y_k = p_k^2 - k^2$
原问题“最大化 $FST(i, j)$ ”就等价于最大化 $\max(|U_i - U_j|, |V_i - V_j|)$ 。这进一步分解为两个独立的子问题：
- 找到序列 $U$ 中的最大差值，即 $\max(U) - \min(U)$ 。
- 找到序列 $V$ 中的最大差值，即 $\max(V) - \min(V)$ 。
最终的答案就是这两个最大差值中的较大者。
实现：
- 我们可以在一次遍历中解决这个问题。
- 迭代 $i$ 从 1到 $n$ ，在循环中计算出当前的 $U_i$ 和 $V_i$ 。
- 同时维护四个变量：max_u, min_u, max_v, min_v，实时更新这两个序列的最大值和最小值。
- 遍历结束后，计算 max_u - min_u 和 max_v - min_v，取其中的较大值即可。
- 由于 $p_i$ 和 $i$ 的值可达 $10^5$ ，它们的平方会达到 $10^{10}$ ，因此需要使用64位整型（long long 或 long）来存储计算结果以避免溢出。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    if (n <= 1) {
        cout << 0 << endl;
        return 0;
    }

    long long p;
    cin >> p;
    long long i = 1;
    long long max_u = p * p + i * i;
    long long min_u = max_u;
    long long max_v = p * p - i * i;
    long long min_v = max_v;

    for (i = 2; i <= n; ++i) {
        cin >> p;
        long long u = p * p + i * i;
        long long v = p * p - i * i;
        max_u = max(max_u, u);
        min_u = min(min_u, u);
        max_v = max(max_v, v);
        min_v = min(min_v, v);
    }

    cout << max(max_u - min_u, max_v - min_v) << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        if (n <= 1) {
            System.out.println(0);
            return;
        }

        long p = sc.nextLong();
        long i = 1;
        long maxU = p * p + i * i;
        long minU = maxU;
        long maxV = p * p - i * i;
        long minV = maxV;

        for (i = 2; i <= n; i++) {
            p = sc.nextLong();
            long u = p * p + i * i;
            long v = p * p - i * i;
            maxU = Math.max(maxU, u);
            minU = Math.min(minU, u);
            maxV = Math.max(maxV, v);
            minV = Math.min(minV, v);
        }

        System.out.println(Math.max(maxU - minU, maxV - minV));
    }
}

n = int(input())
if n <= 1:
    print(0)
else:
    p_values = list(map(int, input().split()))
    
    # 初始化
    p = p_values[0]
    i = 1
    max_u = p * p + i * i
    min_u = max_u
    max_v = p * p - i * i
    min_v = max_v
    
    # 迭代更新
    for idx in range(1, n):
        p = p_values[idx]
        i = idx + 1 # 1-based index
        
        u = p * p + i * i
        v = p * p - i * i
        
        max_u = max(max_u, u)
        min_u = min(min_u, u)
        max_v = max(max_v, v)
        min_v = min(min_v, v)
        
    print(max(max_u - min_u, max_v - min_v))

算法及复杂度

算法：数学变换 + 单次遍历
时间复杂度：我们只需要遍历一次输入的 $n$ 个元素，因此时间复杂度为 $\mathcal{O}(n)$ 。
空间复杂度：我们只用了常数个变量来存储最大值和最小值，因此空间复杂度为 $\mathcal{O}(1)$ 。