POJ 3244 - Difference between Triplets 公式,整合运算

POJ 3244 - Difference between Triplets 公式,整合运算

这道题的关键是一个推论....max(a,b,c)-min(a,b,c)= ( |a-b| + |b-c| + |a-c| ) / 2  把a,b,c放到坐标轴上...是很清晰的...

整合运算...max ( Ix-ly , Jx-Jy , Kx-Ky ) - min (  Ix-ly , Jx-Jy , Kx-Ky ) = ( | lx-ly-Jx+Jy | + | Jx-Jy-Kx+Ky | + | Kx-Ky-Ix+Iy | ) / 2

= ( | (Ix-Jx) - (Iy-Jy) | + | (Jx-Kx) - (Jy-Ky) | + | (Kx-Ix) - (Ky-Iy) | ) /2

因为是要求所有的之和...所以这三个绝对值是互不干扰了...所有的 I-J, J-K, K-I 算出来..排个序..然后再找其做了多少次加法和减法..

如当前是第i大的I-J..那么其做了i-1次加法..n-i次减法..相抵消..做了(i-1-(n-i))次加法...

Program:

#include#include#include#include#include#include#include#include#define ll long long#define oo 1000000007#define pi acos(-1.0)#define MAXN 200005using namespace std; ll a[MAXN],b[MAXN],c[MAXN];int main(){ int n,i; while (~scanf("%d",&n) && n) { for (i=1;i<=n;i++) { int I,J,K; scanf("%d%d%d",&I,&J,&K); a[i]=I-J,b[i]=J-K,c[i]=I-K; } sort(a+1,a+1+n),sort(b+1,b+1+n),sort(c+1,c+1+n); ll ans=0; for (i=1;i<=n;i++) ans+=((i-1-(n-i))*(a[i]+b[i]+c[i])); printf("%I64d\n",ans/2); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。