1、友好的生物解題【摘要】【題意簡述】共有 N (2N100,000)種生物，對(duì)于任意的生物 t(1tN)，都有 K(1K5)種屬性：Pt,1、Pt,2、Pt,K。此外，根據(jù)給定的非負(fù)常數(shù) C1、C2、CK，利用以下公式，可以計(jì)算出任意兩種生物 A 和 B 之間的友好程度：基本思路枚舉+掃描時(shí)間復(fù)雜度O(Nlog2N+2KNK)空間復(fù)雜度O(NK)很顯然，問題的難點(diǎn)就在于，可能的 S 序列共有 2K-1 種，它將隨著生物種類的變化而變化，無法預(yù)先確定。但通過進(jìn)一步分析可以發(fā)現(xiàn)，實(shí)際上，對(duì)于生物 A 和 B，根據(jù)合適的序列 S 得出的友好程度 EA-EB，將比根據(jù)其他各種序列 S得出的友好程度都要大

2、。因?yàn)楦鶕?jù)合適的序列 S，最后的友好程度將等于一系列非負(fù)整數(shù)的和；而如果改變序列 S 中若干項(xiàng)的符號(hào)，也就相當(dāng)于將原來求和式中，對(duì)應(yīng)的非負(fù)整數(shù)改為非正數(shù)，相應(yīng)的和也就不會(huì)增加。也就是說，對(duì)于兩種生物，它們之間真正的友好程度，將等于各種符號(hào)序列所推出的友好程度中最大的一個(gè)。因此，要求所有生物中，友好程度最大的一對(duì)，也就是根據(jù)每種符號(hào)序列分別推出的生物特征值 Ei 中差距最大的一對(duì)。這樣，得出了在只考慮前 K-1 種屬性的前提下，求友好程度最大的一對(duì)生物的方法：枚舉 2K-1 種符號(hào)序列，每次根據(jù)確定的符號(hào)序列 S，計(jì)算出所有生物的特征值 Ei，并找出其中差距最大的一對(duì)（特征值最大的和最小的兩種生

3、物）。最后的也就是那 2K-1 對(duì)生物中，特征值差最大的一對(duì)。解決了上面，就可以將第 K 種屬性也考慮進(jìn)來。由于最后一項(xiàng)2K屬性差值的系數(shù)是-1，如果仍然沿用前面的方法，枚舉出 個(gè)符號(hào)序列，將不能保證生物之間真正的友好程度是根據(jù)各種 S 序列得出的友好程度中最大的一個(gè)。下面，的目標(biāo)就是要消除對(duì)第 K 種屬性值符號(hào)的不確定性。注意到，公式中最后一項(xiàng)屬性差值的系數(shù)為負(fù)值，也就相當(dāng)于每次都用較小的一個(gè)屬性值減去較大的。而對(duì)于兩種生物，一旦確定將第 K 項(xiàng)屬性差值的相反數(shù)（用較小的屬性值減去較大的所得結(jié)果）計(jì)入最后的友好程度，那么前面 K-1 項(xiàng)屬性差值的和，仍就可以根據(jù)前面的方法，通過枚舉符號(hào)序列求

4、得。綜合上面的分析就得出了下面的方法：枚舉前 K-1 項(xiàng)屬性的符號(hào)序列，SK=1；根據(jù)確定的符號(hào)序列S 求出每種生物的特征值 E。那么生同時(shí)不妨假設(shè)物 t 與其他生物的最大友好程度就等于：【算法描述】根據(jù)上面的分析，得出了下面的算法：首先，將所有的生物，按照第 K 種屬性值從大到小排列；然后，枚舉出各種符號(hào)序列（共 2K-1 種），對(duì)于每一種符號(hào)序列 S，求出每種生物的特征值 E，接著依次掃描每種生物，掃描中記下前 i-1 種生物最小的特征值 Min，并且用 Ei-Min 與當(dāng)前最大的友好程度進(jìn)行比較，并且用 Ei 改進(jìn) Min，便于以后的掃描中進(jìn)行比較?！緯r(shí)空復(fù)雜度】空間方面，該算法只需要記

5、下每種生物的各項(xiàng)屬性值，空間復(fù)雜度為 O(NK)。時(shí)間復(fù)雜度方面，第一步排序，由于數(shù)據(jù)給出的屬性值是-10000,10000的整數(shù)，因此可以用一些線性的排序算法，復(fù)雜度為 O(N)；更一般的情況下可以直接使用快速排序等，復(fù)雜度為 O(Nlog2N)。第二步，一共存在著 2K-1 種符號(hào)序列，每次掃描的復(fù)雜度均為 O(NK)，因此總的復(fù)雜度為 O(2KNK)。因此整個(gè)算法的時(shí)間復(fù)雜度就是 O(Nlog2N+2KNK)。【解題小結(jié)】回顧解決本題的過程，原來對(duì)于兩種確定的生物，只可能得出一個(gè)友好程度，卻根據(jù)不同的符號(hào)序列計(jì)算出若干個(gè)友好程度值，使得原來具有差異的計(jì)而算得到了，方便了計(jì)算。同時(shí)，由于這樣的是建立在不影響最后結(jié)果的基礎(chǔ)上的，使得整個(gè)問題得到了的解決。此外，在分析問題時(shí)，先從簡