友好的生物解题报告

1、WC2005SolutionSpecies广东中山一中黄源河友好的生物解题报告【题意简述】一个星球上有N种生物，每种生物都有K种属性，用整数Pi,j表示第i种生物的第j项属性的属性值，则生物a和生物b之间的友好程度可以用如下公式计算：，其中Ci是非负常数。请找出友好程度最大的一对生物。【算法分析】两个生物之间的友好程度计算公式用文字来表达，就是“前K-1项属性的属性差”，减去“第K项属性的属性差”。可见第K项属性是最特殊的，给我们的分析造成了不小的麻烦，所以干脆先不考虑它，把友好程度公式修改成这样：。我们可以先考虑对于这个简化过的友好程度公式，怎样找出友好程度最大的一对生物，然后再回到原问题来

2、讨论。首先我们讨论K=2的情况。这时每种生物只有两种属性，生物a和生物b的友好程度为：Friendliness = | C1*Pa,1 C1*Pb,1 | + | C2*Pa,2 C2*Pb,2 | 。这条式子的几何意义为：平面上点(C1*Pa,1,C1*Pb,1) 和点(C2*Pa,2,C2*Pb,2)之间的距离（这里距离定义为两坐标之差的绝对值之和）。于是，我们可以用平面上N个点表示N种生物，令Pi=(xi,yi)=(Ci*Pi,1,Ci*Pi,2)，我们的任务就是要找出距离最大的两个点。P1P1 P2 P1 P2 情况1 情况2 第一种情况是P1在P2的右上方，这时Friendlines

3、s = |x1-x2|+|y1-y2| = (x1-x2)+(y1-y2) = (x1+y1)-(x2+y2)。第二种情况是P1在P2的右下方，这时Friendliness = |x1-x2|+|y1-y2| = (x1-x2)-(y1-y2) = (x1-y1)-(x2-y2)。若已知点i，则对任意ji，点i和点j的位置关系都是上面两种之一。所以我们可以用这样一个算法，对每个点，求出在它左边，并和它距离最大的那个点到该点的距离：从左到右扫描每个点，设当前扫描到点i，令F1i=xi+yi，F2i=xi-yi，u1和u2分别是前i-1个点中F1和F2值最小的点，即对任意ji，有F1u1=F1j，

4、F2u2=F2j计算i到它左边点的最大距离：maxF1i-F1u1, F2i-F2u2更新u1和u2，处理下一个点。用上述算法，我们可以在O(N) 的时间内，找出每个点左边距离最大的点，从而得到距离最大的两个点。下面讨论K=3的情况。同样，K=3时，我们可以空间内N个点表示N种生物，Pi=(xi,yi,zi)=(Ci*Pi,1, Ci*Pi,2, Ci*Pi,3)。我们的任务就是要找出这N个点中距离最大的两个点。把所有点按x坐标从大到小排序，同样，对任意两个点，有4种位置关系，读者可以自己想象一下。这4种位置关系，对应的友好程度公式为：Friendliness = |x1-x2|+|y1-y2

5、|+|z1-z2| = (x1+y1+z1)-(x2+y2+z2)。Friendliness = |x1-x2|+|y1-y2|+|z1-z2| = (x1+y1-z1)-(x2+y2-z2)。Friendliness = |x1-x2|+|y1-y2|+|z1-z2| = (x1-y1+z1)-(x2-y2+z2)。Friendliness = |x1-x2|+|y1-y2|+|z1-z2| = (x1-y1-z1)-(x2-y2-z2)。参照K=2时的算法，我们不难设计出K=3时的算法。这里不再赘述。对前面两种算法进行代数意义上的分析，我们发现，两者都是先按第一种属性从大到小排序，然后枚举

6、后面K-1种属性的正负性，得到2K-1种情况，最后通过一次扫描分别找出在这2K-1种情况下每种生物前面的与它友好程度最大的生物。对于更高维数的情况，我们也可以设计出同样的算法。下面是算法描述：对所有生物按Pi,1 从大到小排序。序列Ci满足：C1=C1, Ci Ci, -Ci (1i=K)；枚举Ci的取值。依次处理每种生物，设当前处理到第i种生物，令，u是前i-1种生物中F值最小的点，即Fu=Fj (ji)算出生物i与前面的生物间的最大友好程度Fi-Fu，若大于已知最大友好程度，记录i和u。若FiFu 则令u=i；继续处理下一个生物。枚举的Ci次数为2K-1，每次找最大友好程度的复杂度是O(n)，所以总时间复杂度是O(N*2K)（不计排序时间复杂度）。最后让我们回到原来的问题上。原问题的友好程度公式的特殊之处就在于第K项属性差是减而不是加，如果直接套用前面的算法，由于枚举了第K项属性的正负性，第K项属性差的加减实际上是没有意义的，求出来的结果仍然是简化后的问题的结果。其实解决这个问题办法并不困难，我们只需要对原来的算法稍作修改就可以了。注意到在前面的算法中，有一项属性的正负性是不用枚举的，我们默认地把它设为了第一项。而现在为了使第K项属性差的减号有意义，我们不能枚举第K项属性的正负性，所以我们只需要把第K项属性作为不枚举的那项属性就可以了。也就是说，原