题解 | #最大 FST 距离#

题目链接

题目描述

给定 $n$ 个元素，第 $i$ 个元素具有特征值 $a_i$ 。定义两个元素 $i$ 和 $j$ 之间的 FST 距离为： $D(i, j) = |a_i^2 - a_j^2| + |i^2 - j^2|$

请计算所有元素对中的最大 FST 距离。

解题思路

这是一个求解最大距离的问题。如果采用暴力法，遍历所有可能的元素对 $(i, j)$ 来计算距离，时间复杂度将是 $\mathcal{O}(n^2)$ ，对于 $n$ 较大的情况会超时。因此，我们需要对公式进行分析和优化。

1. 公式分析与几何解释 FST 距离的公式 $D(i, j) = |a_i^2 - a_j^2| + |i^2 - j^2|$ 实际上是二维平面上两点之间的曼哈顿距离。我们可以将每个元素 $k$ 看作是平面上的一个点 $P_k$ ，其坐标为 $(x_k, y_k) = (k^2, a_k^2)$ 。这样，FST 距离 $D(i, j)$ 就是点 $P_i$ 和 $P_j$ 之间的曼哈顿距离。问题就转化为了：在由 $n$ 个点组成的点集中，找出曼哈顿距离最远的一对点。

2. 曼哈顿距离与切比雪夫距离的转换 直接在点集中寻找最远曼哈顿距离仍然不容易。这里有一个重要的几何变换技巧：将坐标系旋转45度，可以实现曼哈顿距离和切比雪夫距离的相互转换。

3. 问题简化 现在，问题变成了在新坐标系中寻找最远的切比雪夫距离。一个点集中最远的切比雪夫距离为： $\max_{i,j} (\max(|u_i - u_j|, |v_i - v_j|)) = \max(\max_{i,j}|u_i - u_j|, \max_{i,j}|v_i - v_j|)$ 而 $\max_{i,j}|u_i - u_j|$ 就是所有 $u$ 值中的最大值与最小值的差，即 max(u) - min(u)。同理， $\max_{i,j}|v_i - v_j| = \text{max}(v) - \text{min}(v)$ 。

所以，最终的最大 FST 距离就是 max(max(u) - min(u), max(v) - min(v))。

4. 算法步骤

根据原问题，我们定义的点的坐标是 $(i^2, a_i^2)$ 。
进行坐标变换，计算每个元素 $i$ 对应的新坐标分量 $u_i$ 和 $v_i$ ：
- $u_i = i^2 + a_i^2$
- $v_i = i^2 - a_i^2$
我们只需要遍历一次所有元素，在遍历过程中同时找出 $u_i$ 的最大值、最小值和 $v_i$ 的最大值、最小值。
计算出 max_u - min_u 和 max_v - min_v。
这两者中的较大值就是我们要求的最大 FST 距离。

这个算法只需要一次遍历，时间复杂度为 $\mathcal{O}(n)$ 。由于 $i^2$ 和 $a_i^2$ 的值可能很大，需要使用长整型（long long）来存储。

代码

c++
java
python

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    long long max_u = -2e18, min_u = 2e18;
    long long max_v = -2e18, min_v = 2e18;
    
    for (long long i = 1; i <= n; ++i) {
        long long a;
        cin >> a;
        
        long long u = i * i + a * a;
        long long v = i * i - a * a;
        
        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;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }
        
        long maxU = Long.MIN_VALUE;
        long minU = Long.MAX_VALUE;
        long maxV = Long.MIN_VALUE;
        long minV = Long.MAX_VALUE;
        
        for (long i = 0; i < n; i++) {
            long idx = i + 1;
            long val = a[(int)i];
            
            long u = idx * idx + val * val;
            long v = idx * idx - val * val;
            
            maxU = Math.max(maxU, u);
            minU = Math.min(minU, u);
            maxV = Math.max(maxV, v);
            minV = Math.min(minV, v);
        }
        
        long dist = Math.max(maxU - minU, maxV - minV);
        System.out.println(dist);
    }
}

import sys

def solve():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    
    max_u = -float('inf')
    min_u = float('inf')
    max_v = -float('inf')
    min_v = float('inf')
    
    for i in range(n):
        idx = i + 1
        val = a[i]
        
        u = idx*idx + val*val
        v = idx*idx - val*val
        
        max_u = max(max_u, u)
        min_u = min(min_u, u)
        max_v = max(max_v, v)
        min_v = min(min_v, v)
        
    result = max(max_u - min_u, max_v - min_v)
    print(result)

solve()

算法及复杂度

算法：坐标变换 + 单次遍历
时间复杂度：我们只需要对输入数组进行一次遍历，以找到变换后坐标分量的最大值和最小值。因此，总时间复杂度为 $\mathcal{O}(n)$ 。
空间复杂度：我们只需要常数个变量来存储最大值和最小值，因此空间复杂度为 $\mathcal{O}(1)$ （不考虑输入数组的存储）。