2020百度之星初赛二 Distance

本文主要是介绍2020百度之星初赛二 Distance，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem Description
小沃沃所在的世界是一个二维平面。他有 n 个朋友，第 i 个朋友距离他的距离为 a[i]，小沃沃并不知道这些朋友具体在什么点上。

请问在最优情况下，小沃沃的朋友两两之间的欧几里得距离的和的最小值是几？

假设小沃沃的位置为 P0=(x0,y0)，第 i 个朋友的位置为 Pi=(xi,yi)，对于所有的 i，需要满足 dist(P0,Pi)=a[i]，并且∑n−1i=1∑nj=i+1dist(Pi,Pj) 最小，其中 dist(X,Y) 为连接点 X 和点 Y 的线段的长度。xi,yi 都可以是任意实数。

Input
第一行一个正整数 test(1≤test≤10) 表示数据组数。

对于每组数据，第一行一个正整数 n(1≤n≤100000)。

接下来一行 n 个整数，第 i 个整数 ai 表示第 i 个朋友和小沃沃的距离。

Output
对每组数据输出一行一个数，表示 ∑n−1i=1∑nj=i+1dist(Pi,Pj) 的最小值。答案需要四舍五入到整数。

Sample Input
2
2
3 5
5
1 2 3 4 5

Sample Output
2
20

Source
2020 年百度之星·程序设计大赛 - 初赛二

思路：
肯定排在一条线上最优。
这种求相互之间的距离和可以想想递推。
将点按距离排序，定义 $f [i]$ 为前i个点的距离和，然后推出递推式就好了。
$f [i] = f [i - 1] + (d [i] - d [i - 1]) * (i - 1);$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include <map>
#include <string>using namespace std;
typedef long long ll;typedef long long ll;
const int maxn = 1e5 + 7;
const int mod = 1e9 + 7;ll d[maxn],f[maxn];int main() {int T;scanf("%d",&T);while(T--) {int n;scanf("%d",&n);for(int i = 1;i <= n;i++) {scanf("%lld",&d[i]);}sort(d + 1,d + 1 + n);for(int i = 1;i <= n;i++) {f[i] = f[i - 1] + (d[i] - d[i - 1]) * (i - 1);}ll ans = 0;for(int i = 1;i <= n;i++) ans += f[i];printf("%lld\n",ans);}return 0;
}