A.begin
一道显而易见的结论题
因为\(a^2+b^2\leq (a+b)^2\),所以排个序，算一下（1,2），（i，i-2）···（n-1,n)的路长的和，即得答案
AC Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
inline ll read()
{
ll x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
int n;
ll w[N];
int main()
{
n=read();
for(int i=1;i<=n;i++)w[i]=read();
sort(w+1,w+n+1);
ll ans=0;
for(int i=2;i<=n;i++)
{
if(i==2)
{
ans+=(w[2]-w[1])*(w[2]-w[1]);
continue;
}
ans+=(w[i]-w[i-2])*(w[i]-w[i-2]);
}
ans+=(w[n]-w[n-1])*(w[n]-w[n-1]);
printf("%lld",ans);
return 0;
}
B.arrive
画个图就可以知道，一定是两个城市互为对方的庇护所，所以可行的n一定是一个偶数。
把城市两两匹配，然后根据大小关系来求答案