[LOJ520] 绯色 IOI（开端）- 贪心

Description

给定一张无向完全图，每个点给定一个点权，每条边的权值是它连接的两个点的点权的差的平方，求权值和最小的哈密顿回路。

Solution

由于哈密顿回路一定经过每一个点，所以每个 (x_i^2) 必定恰好在结果中出现两次，因此我们只需要最小化交叉乘积项，即最大化 (sum x_i x_{i+1}) 即可。

将所有边权从小到大排序后，显然最终的结果一定是 (x_1x_2+x_1x_3+x_2x_4+x_3x_5+...+x_{n-2}x_n+x_{n-1}x_n)。

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 1000005;

int n,a[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++) cin>>a[i], sum+=a[i]*a[i];
    sort(a+1,a+n+1);
    int ans=a[1]*a[2]+a[n-1]*a[n];
    for(int i=1;i+2<=n;i++) ans+=a[i]*a[i+2];
    cout<<2*(sum-ans)<<endl;
    return 0;
}