额额。看起来很水,感觉很容易就能推出递推式子来,但是第一次前缀和竟然没用好,导致WA了一板刷,真心不好。。。。。
其实只要算出来每次增加一个点对于ans的贡献就好,然后用前缀和来维护sum,i从2->n跑一遍,然后输出2*ans就好了。
因为题目中把线段ab和线段ba当做了不同的线段来处理。。。。
关于递推式子的推导: (a[n] - a[n-1])+(a[n]-a[n-2])+( a[n]-a[n-3])+...+(a[n]-a[0] ) = a[n]*(n-1)-(a[n-1]+a[n-2]+...+a[1]) = a[n]*(n-1)-sum[n-1];
# include<cstdio> # include<iostream> # include<algorithm> using namespace std; # define MAX 12345 typedef long long LL; LL sum,ans; LL a[MAX]; int main(void) { int n;cin>>n; for ( int i = 1;i <= n;i++ ) scanf("%lld",&a[i]); sort(a+1,a+1+n); sum = a[1]; for ( int i = 2;i <= n;i++ ) { ans += (LL)a[i]*(i-1)-sum; sum+=a[i]; } printf("%lld\n",ans<<1); return 0; }