A. Great Graphs

https://codeforces.com/problemset/problem/1540/A
思路
找规律，要使总路程最小，那么就把所有的点都连在同一条线上，然后只连一条正权边，然后再把其他所有可以连的边都连成负的，然后所有的边权相加。

问题在于找到负权边的规律。也就是找到每个位置的边被计算的次数。

规律是每条边左右对称的位置 * （边数 -1），然后（边数 -1）+（边数 - 2），依次累加，见代码中的times，和cnt操作

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100005;
signed main()
{
    int T; cin >> T;while(T -- ){
    int n, num[N]; cin >> n;for(int i = 0; i < n; i ++ ){
    cin >> num[i];}sort(num, num + n);for(int i = n - 1; i > 0; i -- ){
    num[i] = num[i] - num[i - 1];}int times = n - 1;//点数-1是边数int cnt = times;int ans = 0;for(int i = 1, j = n - 1; i < j; i ++, j -- ){
    ans -= (num[i] + num[j]) * (times - 1);cnt -= 2;times += cnt;} if(n%2 == 0){
    ans -= (num[n/2]) * (times - 1);}cout << ans << endl;}return 0;
}