C++14(g++5.4) 解法, 执行用时: 74ms, 内存消耗: 888K, 提交时间: 2020-09-22 11:37:49

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int N=1e5+9;
const ll mo=1e9+7;
int n,a[N],l,r,mid;
ll m,s;
ll cnt(int p)
{
	ll s=0; int j=1;
	while(j<n&&a[1]+a[j]<=p) j++;
	fo(i,1,n)
	{
		while(j&&a[i]+a[j]>p) j--;
		s+=j;
	}
	return s;
}
int main()
{
	cin>>n; m=1ll*n*n+1>>1;
	fo(i,1,n) cin>>a[i];
	sort(a+1,a+n+1);
	for(l=a[1]*2,r=a[n]*2;l<r;)
	{
		mid=l+r>>1; ll t=cnt(mid);
		t>=m?r=mid:l=mid+1;
	}
	fo(i,1,n) a[i]=abs(a[i]*2-l);
	sort(a+1,a+n+1);
	fo(i,1,n) s=(s+a[i]*(2*i-1ll))%mo;
	cout<<s;
}

C++11(clang++ 3.9) 解法, 执行用时: 395ms, 内存消耗: 1256K, 提交时间: 2020-09-24 09:42:48

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

const int N=100010;
int a[N],n,b[N];

long long check(int x){
	long long ans=0;
	for(int i=1;i<=n;i++) b[i]=abs(a[i]-x);
	sort(b+1,b+1+n);
	for(int i=1;i<=n;i++) ans+=1ll*b[i]*(i+i-1);
	return ans;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]*=2;
	sort(a+1,a+1+n);
	int L=a[1],R=a[n];
	while(L<R){
		int mid1=L+(R-L)/3,mid2=R-(R-L)/3;
		if(check(mid1)<check(mid2)) R=mid2-1;
		else L=mid1+1;
	}
	printf("%lld\n",check(L)%1000000007);
}