最大 FST 距离

思路

题目定义了 FST 距离：对于元素对 ，距离为 （下标从 1 开始）。要求所有元素对中的最大距离。

暴力枚举所有对是 ，数据量大了肯定超时。有没有 的做法？

绝对值拆解技巧

遇到 求最大值这种形式，有个经典套路——展开绝对值。 等于以下四个表达式中的最大值：

$$

令 ，，展开后每种情况都能拆成"只和 有关的部分"减去"只和 有关的部分"：

发现了吗？第 3 种和第 2 种互为相反数，第 4 种和第 1 种互为相反数。所以要取四者最大值，其实只需要关注两个差的绝对值：

$$

做法

对每个元素 ，计算 和 ，一遍扫描维护 和 的最大最小值，答案就是 。

一遍扫过去， 搞定。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    long long mx1 = LLONG_MIN, mn1 = LLONG_MAX;
    long long mx2 = LLONG_MIN, mn2 = LLONG_MAX;
    for(int i = 1; i <= n; i++){
        long long a;
        cin >> a;
        long long a2 = a * a;
        long long i2 = (long long)i * i;
        long long s = a2 + i2;
        long long d = a2 - i2;
        mx1 = max(mx1, s); mn1 = min(mn1, s);
        mx2 = max(mx2, d); mn2 = min(mn2, d);
    }
    cout << max(mx1 - mn1, mx2 - mn2) << endl;
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        long mx1 = Long.MIN_VALUE, mn1 = Long.MAX_VALUE;
        long mx2 = Long.MIN_VALUE, mn2 = Long.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            long a = Long.parseLong(st.nextToken());
            long a2 = a * a;
            long i2 = (long) i * i;
            long s = a2 + i2;
            long d = a2 - i2;
            mx1 = Math.max(mx1, s);
            mn1 = Math.min(mn1, s);
            mx2 = Math.max(mx2, d);
            mn2 = Math.min(mn2, d);
        }
        System.out.println(Math.max(mx1 - mn1, mx2 - mn2));
    }
}

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
mx1 = mn1 = a[0]**2 + 1
mx2 = mn2 = a[0]**2 - 1
for i in range(1, n):
    idx = i + 1
    a2 = a[i] ** 2
    i2 = idx * idx
    s = a2 + i2
    d = a2 - i2
    if s > mx1: mx1 = s
    if s < mn1: mn1 = s
    if d > mx2: mx2 = d
    if d < mn2: mn2 = d
print(max(mx1 - mn1, mx2 - mn2))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const a = lines[1].split(' ').map(s => BigInt(s));
    let mx1 = -1000000000000000000n, mn1 = 1000000000000000000n;
    let mx2 = -1000000000000000000n, mn2 = 1000000000000000000n;
    for (let i = 0; i < n; i++) {
        const idx = BigInt(i + 1);
        const a2 = a[i] * a[i];
        const i2 = idx * idx;
        const s = a2 + i2;
        const d = a2 - i2;
        if (s > mx1) mx1 = s;
        if (s < mn1) mn1 = s;
        if (d > mx2) mx2 = d;
        if (d < mn2) mn2 = d;
    }
    const ans = (mx1 - mn1) > (mx2 - mn2) ? (mx1 - mn1) : (mx2 - mn2);
    console.log(ans.toString());
});

复杂度

时间复杂度 空间复杂度
复杂度

总结

这题核心就是 的绝对值拆解。遇到两个绝对值之和求极值，先想想能不能拆成"只和一个变量有关"的形式。拆完之后维护个最大最小值就行了，从 直接降到 。这个技巧在曼哈顿距离相关的题目里也很常见，值得记住。