C++11(clang++ 3.9) 解法, 执行用时: 45ms, 内存消耗: 988K, 提交时间: 2020-03-25 17:08:05

#include<bits/stdc++.h>
#define maxn 100010
#define ll unsigned long long
using namespace std;
int a[maxn],n;
ll f[maxn],g[maxn],ans;
ll s1(int x)
{
	return 1LL*x*(x+1)/2;
}
ll s2(int x)
{
	return 2LL*s1(x/2)-(x/2)*(~x&1);
}
int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
		sort(a+1,a+n+1),ans=1ULL<<63,f[0]=g[n+1]=0;
		for(int i=1;i<=n;i++)
		f[i]=f[i-1]+s2(a[i]-1);
		for(int i=n;i;i--)
		g[i]=g[i+1]+s1(a[i]);
		for(int i=1;i<=n;i++)
		ans=min(ans,s2(a[i]-1)*(i-1)-f[i-1]+g[i+1]-s1(a[i])*(n-i));
		printf("%llu\n",ans);
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 130ms, 内存消耗: 4300K, 提交时间: 2020-06-09 08:49:14

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define V 1000000
#define LL long long
using namespace std;
int n,p[V+5];
int main()
{
	RI i,x,t;LL f,g;W(~scanf("%d",&n))
	{
		for(g=i=0;i<=V;++i) p[i]=0;for(i=1;i<=n;++i) scanf("%d",&x),++p[x],g+=1LL*x*(x+1)/2;
		LL ans=1e18;for(f=t=0,i=0;i<=V;++i) f+=1LL*t*((i-1)/2),f+g<ans&&(ans=f+g),t+=p[i],g-=1LL*(n-t)*(i+1);
		printf("%lld\n",ans);
	}return 0;
}