链接：点击打开链接
题意：给出n个三元组(n<=200000)，定义D(i,j)=max(xi-xj,yi-yj,zi-zj)-min(xi-xj,yi-yj,zi-zj)，求任意两点的D的和
代码：
#include <bitset> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; long long a[400005],b[400005],c[400005]; int main(){ long long n,i,x,y,z,ans; //将xi-xj,yi-yj,zi-zj放在数轴上， while(scanf("%I64d",&n)!=EOF&&n){ //则max(xi-xj,yi-yj,zi-zj)-min(xi-xj,yi-yj,zi-zj) for(i=1;i<=n;i++){ //为三点所形成的线段的长度。但是不知道大小关系，因此 scanf("%I64d%I64d%I64d",&x,&y,&z); //用(|(xi-xj)-(yi-yj)|+|(xi-xj)-(zi-zj)|+|(yi-yj)-(zi-zj)|)/2 a[i]=x-y; //来表示线段长度，化简后得(|(xi-yi)-(xj-yj)|+|(xi-zi)-(xj-zj)|+|(yi-zi)-(yj-zj)|)/2 b[i]=x-z; //令xi-yi=ai,xi-zi=bi,yi-zi=ci,因此变为(|ai-aj|+|bi-bj|+|ci-cj|)/2， c[i]=y-z; //所以分别将a,b,c排序,算出每个点的贡献值 } sort(a+1,a+n+1); sort(b+1,b+n+1); sort(c+1,c+n+1); ans=0; for(i=1;i<=n;i++){ ans+=(i-1)*a[i]+(-1)*(n-i)*a[i]; ans+=(i-1)*b[i]+(-1)*(n-i)*b[i]; ans+=(i-1)*c[i]+(-1)*(n-i)*c[i]; } printf("%I64d\n",ans/2); } return 0; }
