题解 | 最大 FST 距离

本题使用切比雪夫不等式将双变量问题转化为单变量问题，从而使用一层循环即可实现，极大地降低时间复杂度。

#include <iostream>
using namespace std;
int main(){
    long long n,a;
    long long u,v,max_u,min_u,max_v,min_v,dist;
    cin>>n;
    if(n==1){
        cout<<0;
        return 0;
    }
    for(long long i=1;i<=n;i++){          //注意把i改为long long类型，这样得到的u、v也是long long类型
        cin>>a;
        u=a*a+i*i;
        v=a*a-i*i;
        if(i==1){
            max_u=min_u=u;
            max_v=min_v=v;
        }
        else{
            max_u=max(max_u,u);
            min_u=min(min_u,u);
            max_v=max(max_v,v);
            min_v=min(min_v,v);
        }
    }
    dist=max(max_u-min_u,max_v-min_v);
    cout<<dist;
    return 0;
}