题单贴贴
A.Begin
- 这是道结论题。但令人惊奇的是我
完全没往这方面想用奇怪的策略做居然得到了 \(\mathtt{80pts}\)；
Solution
-
观察样例，再结合一点数学知识，我们可以知道当每一对 \(a\) 和 \(b\) 相差尽可能小的时候，答案有最小值。考虑排序，但 \(min\) 值与 \(max\) 值这一对产生的贡献很可能巨大，所以要避免这种情况的发生。
-
得到结论为将 \((w_1,w_2)\)、\((w_{n-1},w_n)\) 连接，对于 \(i\in [1,n-2]\)，将每一对 \((w_i,w_{i+2})\) 相连即可；
AC code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
s=s*10+int(ch-'0');
ch=getchar();
}
return s*f;
}
#define ll long long
const int N=1e6+10;
int n;
int w[N];
ll ans=0;
int main(){
n=read();
for(int i=1;i<=n;++i)
w[i]=read();
sort(w+1,w+n+1);
ans+=1ll*(w[1]-w[2])*(w[1]-w[2])+1ll*(w[n-1]-w[n])*(w[n-1]-w[n]);
for(int i=1;i<n-1;++i)
ans+=1ll*(w[i]-w[i+2])*(w[i]-w[i+2]);
printf("%lld",ans);
return 0;
}