00:00/00:00

题目传送门

题意:

给出很多三元组,两个三元组,然后两个三元组的距离差就是

ans=max(x_1-x_2,y_1-y_2,z_1-z_2)+min(x_1-x_2,y_1-y_2,z_1-z_2)

然后我们要计算任意两组之间的距离之和。。。
## 分析:
我们可以得到如下推论:
a = x1-x2, b=y1-y2, c=z1-z2
ans = max (a,b,c) − min (a,b,c)
ans=\frac {(|a_1-a_2|+|b_1-b_2|+|c_1-c_2|)}{2}
ans=\frac {|a_1-a_2|}{2}+\frac {|b_1-b_2|}{2}+\frac {|c_1-c_2|}{2}
ans = \frac {|(x1-y1)-(x2-y2)|}{2}+\frac {|(y1-z1)-(y2-z2)|}{2}+\frac {|(z1-x1)-(z2-x2)|}{2}

我们让a数组存(x-y)。。。同理。。。
然后我们考虑每一个数字要被加几次,减几次,然后我们得到结论:ai总的贡献是 [i+i-n+1] * a_i
然后就算好啦。。。

代码:

#include        <set>
#include        <map>
#include      <queue>
#include      <stack>
#include      <cmath>
#include     <cstdio>
#include     <time.h>
#include     <vector>
#include    <cstring>
#include   <stdlib.h>
#include   <iostream>
#include  <algorithm>
#define LL long long 
#define lowbit(x) x &(-x)
using namespace std;
const LL N=2e5+10;
const LL mod=998244353;
const LL inf=1e17;
namespace FastIO
{
    template<typename tp> inline void read(tp &x)
    {
        x=0; char c=getchar(); bool f=0;
        for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template<typename tp> inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template<typename tp> inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int n;
int a[N],b[N],c[N];
int main()
{
    while(~scanf("%d",&n))
    {
        if(!n)break;
        for(int i=1;i<=n;i++)
        {
            int x,y,z;
            read(x),read(y),read(z);
            a[i]=x-y;b[i]=y-z;c[i]=z-x;
        }
        sort(a+1,a+n+1);
        sort(b+1,b+n+1);
        sort(c+1,c+n+1);
        LL ans=0;
        for(int i=1;i<=n;i++)
        {
            ans+=1LL*(i*2-n+1)*a[i];
            ans+=1LL*(i*2-n+1)*b[i];
            ans+=1LL*(i*2-n+1)*c[i];
        }
        writeln(ans/2);
    }
    return 0;
}

1 Comments

发表评论

电子邮件地址不会被公开。 必填项已用*标注