友好的生物解題報告

《友好的生物》解題

省蕪湖市第一中學(xué)

朱晨光

【問題描述】

給定K個非負(fù)常數(shù)Ci以及N個生物各自的K個屬性。定義任兩個生物的友

好程度

效果也并不太好。因此，

須想出一個優(yōu)秀的算法來降低時間復(fù)雜度。

注意到題目中有一個條件很特別，就是K≤5.前面的枚舉算法只是關(guān)注N，而忽略了K。那么，如此小的K是否可以作為解題的突破口呢？首先，讓

來看一個此問題的簡化版——即讓第K個屬性的差別也加到友好程度中，而不是減去。

因為

Ci非負(fù)，所以有Ci*|Ai,t-Bi,t|=|

i,t-Ci*Bi,t|.

因此，為了方便處理，在

處理數(shù)據(jù)時不妨讓每個生物的每個屬性都乘以對應(yīng)的常數(shù)。這樣問題就變得更加

簡單了：給定N*K個數(shù)

A1,1,A1,2,A1,3,……,A1,K,A2,1,A2,2,……AN,1,AN,2,……,

.

試求一對i,j(i≠j)，使得

呢？因為

希望整個式子的值盡量大，于是|Ai,k-Aj,k|就要盡量小，但是上面的

枚舉符號是基于|a-b|=max(a-b,b-a)，如果單純地對于第k維也這么做，就會把一

個

最大值當(dāng)成結(jié)果輸出（如:-|3-5|,會算成-3+5=2，與實際不符）。那么，應(yīng)

該如何解決這個問題呢？

與其思考如何改造第k維，使得上面的算法依然成立，倒不如將第k維提出來單獨考慮。具體地說，就是把所有生物按照第k維的值從小到大排序。這樣就有：

Ai,k-Aj,k

i<j

-|Ai,k-Aj,k|=

Aj,k-Ai,k

j<i

由于

可以在枚舉時只考慮i<j的情況，所以只要將每個Sj都減去Aj,k就

可以了。剩下的操作依然是選擇一個最大的Sj.這個算法與前文的算法十分類似，

不同的地方僅在于需要先按照第k維的值從小到大排序，再修改流程如下：

Sj的值即可。

這個算法的時間復(fù)雜度為O(NlogN+2k-1N)（注意這里是2k-1,而并非2k，因為第k維的符號不需要枚舉）,對于解決這道題目已經(jīng)綽綽有余了。

【更進(jìn)一步的探討】

這個算法的時間復(fù)雜度仍含有指數(shù)2k-1，能否找到真正意義上的多項式算法，使得對于較大的k值也能輕松解決，值得進(jìn)一步的探討。

【總結(jié)】

解決這道題目的關(guān)鍵在于選擇K為突破口并利用絕對值符號的一些性質(zhì)，對第k維的處理也很重要?？偟膩碚f，解決這類題目的要領(lǐng)在于攻其軟肋，開拓

思路，從而迅速找到方便快捷的解題

。

【附錄】

O(NlogN+2k-1N)算法的程序：species.cpp

1、將各種生物按照第k維的值從小到大排序

2、枚舉前(k-1)維對應(yīng)的式子的符號

3、對于每個生物，計算S值為前(k-1)維的屬性乘以對應(yīng)的符號-第k

維的值

4、掃描一遍，得到Ti=max{Sj|i<=j<=N}，∏i=Ti所選擇的j

5、枚舉i(1<=i<N)，tempresult=第i個生物前(k-1