题解 | 最大 FST 距离

C++ 注意下标 10^5*10^5 = 10^10 > 2*10^9超出 int 表示范围

#include <climits>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a;
    while (n--) {
        int ai;
        cin >> ai;
        a.push_back(ai);
    }
    // |i^2-j^2| + |Ai^2-Aj^2| ==> |xi-xj| + |yi-yj| 之间的曼哈顿距离
    // 有 |xi-xj| + |yi-yj| = max(|(xi+yi)-(xj+yj)|, |(xi-yi)-(xj-yj)|)
    // 即 max(xi+yi)-min(xj+yj) 和 max(xi-yi)-min(xj-yj)
    long long max_s=LLONG_MIN, max_d=LLONG_MIN;
    long long min_s=LLONG_MAX, min_d=LLONG_MAX; 
    long long xi, yi, s, d;
    for (int i=1; i<=a.size(); i++) {
        xi = (long long)i*i; yi = a[i-1]*a[i-1];
        s = xi+yi; d = xi-yi;
        if (s>max_s) max_s=s;
        if (s<min_s) min_s=s;
        if (d>max_d) max_d=d;
        if (d<min_d) min_d=d;
    }
    cout << max(max_s-min_s, max_d-min_d);
}
// 64 位输出请用 printf("%lld")