题解 | 最大 FST 距离

#include <iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<cmath>
#define ll long long
//      |i^2-j^2|+|Ai^2-Aj^2|  进行去绝对值 并将i,j移到一边 得到4种情况：
//      （i^2+Ai^2）-(j^2+Aj^2)    1
//       -(i^2+Ai^2)+(j^2+Aj^2)    2
//      （i^2-Ai^2）-(j^2-Aj^2)    3             
//      -(i^2-Ai^2）+(j^2-Aj^2)    4
//      
//       令：K1=n^2+An^2;   上面1-2式子得到最大值都是：最大K1减最小K1
//       令：K2=n^2-An^2;   上面3-4式子得到最大值都是：最大K2减最小K2    
int main() {
   vector<ll>v;
   vector<ll>v_k1;
   vector<ll>v_k2;
   ll n;
   cin>>n;
   for(ll i=0;i<n;i++){
      ll a;
      cin>>a;
      v.push_back(a);
   }
   for(ll i=0;i<n;i++){
      ll k1,k2;
      k1=(i+1)*(i+1)+v[i]*v[i];
      v_k1.push_back(k1);
      k2=(i+1)*(i+1)-v[i]*v[i];
      v_k2.push_back(k2);
   }
   sort(v_k1.begin(),v_k1.end());
   sort(v_k2.begin(),v_k2.end());
   ll FSTmax=0;
   FSTmax=max(v_k1[n-1]-v_k1[0],v_k2[n-1]-v_k2[0]);
   cout<<FSTmax;
  
   
}
// 64 位输出请用 printf("%lld")