Distance 链接：https://ac.nowcoder.com/acm/problem/14268 来源：牛客网
FST作为小朋友，经常会遇到和距离有关的问题，但是他已经厌倦了曼哈顿距离和欧几里德距离，所以FST就定义了一种FST距离。 这种距离并不用于空间或平面中，而运用于FST发明的一些神奇的算法中（唔… …）。 设i号元素的特征值为Ai，则i和j的FST距离是
|i2 - j2|+|Ai 2 - Aj2|。
为了实现某新的数据结构，FST想在一大堆元素中找出距离最大的一对元素，他不关心是哪一对元素，只想求出最大距离。
输入 2 4 3 输出 10
对于绝对值的情况进行分类讨论即可，有4种情况，但由于对称性，最后其实是两种情况
1.i2+Ai2-(j2+Aj2) 2.i2-Ai2-(j2-Aj2)
这样就可以表示归纳成为两类数据，一为i2+Ai2,二为i2-Ai2 就可以O（n）了。
#include<cstdio> #include<iostream> #include<cmath> #include<vector> #include<stack> #include<cstring> #include<queue> #include<algorithm> using namespace std; typedef long long ll; int n; ll a[100005]; int main(){ #ifdef LOCAL freopen(".\\a.in", "r", stdin); #endif scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); ll maxx1=0,minn1=99999999999999999; ll maxx2=-99999999999999,minn2=99999999999999999; for(ll i=1;i<=n;i++){ if(i*i+a[i]*a[i]>maxx1)maxx1=i*i+a[i]*a[i];//类别1的最大值 if(i*i+a[i]*a[i]<minn1)minn1=i*i+a[i]*a[i];//类别1的最小值 if(i*i-a[i]*a[i]>maxx2)maxx2=i*i-a[i]*a[i];//类别2的最大值 if(i*i-a[i]*a[i]<minn2)minn2=i*i-a[i]*a[i];//类别2的最小值 } ll ans1,ans2; ans1=maxx1-minn1; ans2=maxx2-minn2; printf("%lld\n",max(ans1,ans2)); return 0; }