分析 对于三元组 {x1,y1,z1},{x2,y2,z2} ，我们设
⎧⎩⎨⎪⎪a1=x1−x2b1=y1−y2c1=z1−z2 然后，在数轴上画出 a1,b1,c1 ，可以发现 max−min=|a1−b1|+|b1−c1|+|c1−a1|2 那么这里就可以先预处理出所有的 ai,bi,ci ，然后升序排序，可以发现对于 ai,aj 如果 ai>aj 那么在计算时， ai 应该是正的，而 aj 应为负的，那么我们分开枚举，对于 ai 它贡献了 (i−1) 次正数，贡献了 (n−i) 次负数，那么总贡献就为 2∗i−n−1 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int MAXN=2000000+10; LL a[MAXN],b[MAXN],c[MAXN]; LL n,ans,a1,b1,c1; bool cmp(const int A,const int B){return A<B;} int main() { while(scanf("%lld",&n)!=EOF) { if(n==0) return 0; memset(a,0,sizeof a); memset(b,0,sizeof b); memset(c,0,sizeof c); for(int i=1;i<=n;i++) { scanf("%lld%lld%lld",&a1,&b1,&c1); a[i]=a1-b1,b[i]=b1-c1,c[i]=c1-a1; } sort(a+1,a+n+1,cmp); sort(b+1,b+n+1,cmp); sort(c+1,c+n+1,cmp); ans=0; for(int i=1;i<=n;i++) ans=ans+(2*i-n-1)*(a[i]+b[i]+c[i]); printf("%lld\n",ans/2); } return 0; }