【叉姐的魔法训练第一课_初级魔法练习】poj 3244 Difference between Triplets (数学)

题目链接

题意:

For every pair of triplets, Ta = (Ia, Ja, Ka) and Tb = (Ib, Jb, Kb), we define the difference value between Ta andTb as follows:

D(Ta, Tb) = max {IaIb, JaJb, KaKb} − min {IaIb, JaJb, KaKb}

Now you are given N triplets, could you write a program to calculate the sum of the difference values between every unordered pair of triplets?

思路:转化要求的式子,如果把IaIb, JaJb, KaKb 看成数轴上的点,所求的式子就变成了求三个点构成的线段的距离。

设X=IaIb,Y=JaJb,Z=KaKb,那么该距离D = (|X-Y| + |Y-Z| + |Z-X|  )/2(该式子是此题最关键的一部,可以通过画图直观得到)  

D=|(ia-ja)-(ib-jb)| + |(ja-ka)-(jb-kb)| + | (ka-za)+(kb-zb) |

设a = ia-ja,b =ja-ka,c = ka-ia,然后分别排序类似于bzoj1604_拆点求曼哈顿距离

考虑第i个a,对于其他的n-1个a,有i-1个比它小,n-i个比它大,因此对答案的贡献为(i-1)个a[i]和 (n-i)个-a[i]

b,c同理。

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz