友好的動(dòng)物的解題報(bào)告

友好的動(dòng)物解題報(bào)告廣東中山紀(jì)念中學(xué) 陳啟峰【問題描述】W星球是一個(gè)和地球一樣氣候適宜、物種聚集的星球。經(jīng)過多年的研究，外星生物學(xué)家們已經(jīng)發(fā)現(xiàn)了數(shù)萬種生物，而且這個(gè)數(shù)字還在不斷增大。W星球上的生物很有趣，有些生物之間很友好，朝夕相伴，形影不離；但有些卻很敵對(duì)，一見面就難免發(fā)生戰(zhàn)斗。為了能夠更好地了解它們之間的友好程度，外星生物學(xué)家希望進(jìn)行一些量化的計(jì)算。他們發(fā)現(xiàn)，兩種生物之間的友好程度和它們的k種屬性有關(guān)，暫且將它們編號(hào)為屬性1、屬性2、屬性k，這些屬性都是可以進(jìn)行量化的。外星生物學(xué)家研究發(fā)現(xiàn)，如果前k-1種屬性的差別越大，這兩種生物就越友好；但是屬性k與眾不同，這種屬性差別越小的兩種生物越友好。因此他們猜想是不是可以用這樣一個(gè)公式量化兩種生物之間的友好程度：，其中Ci是非負(fù)常數(shù)。如果知道了每種生物的各種屬性，利用上述公式就很容易算出它們之間的友好程度了。現(xiàn)在，外星生物學(xué)家們想問一問：在目前發(fā)現(xiàn)的這些生物當(dāng)中，關(guān)系最友好的那對(duì)生物是哪一對(duì)呢？它們之間的友好程度是多少？【問題分析】【數(shù)學(xué)模型】首先，把題目的任務(wù)轉(zhuǎn)化為簡明的數(shù)學(xué)語言：令,求出兩種動(dòng)物的編號(hào)：1=ab=n使得目標(biāo)函數(shù) 最大化?！驹妓惴ǖ拿堋匡@然最原始的算法是枚舉所有可能的a和b，求出最大的。但這樣做程序的時(shí)間復(fù)雜度是O（nk），顯然無法通過所有的數(shù)據(jù)。【數(shù)據(jù)范圍分析】一個(gè)很顯眼的條件k5，便令人不禁會(huì)想到時(shí)間復(fù)雜度為(n2)、（nk!），（nlogn）之類的指數(shù)級(jí)算法,并促使人向該方面的算法思考?！緮?shù)據(jù)結(jié)構(gòu)優(yōu)化時(shí)的矛盾】考慮從數(shù)據(jù)結(jié)構(gòu)上優(yōu)化原始算法。首先，把函數(shù)中的絕對(duì)值去掉，目標(biāo)函數(shù)變成 其中小括號(hào)內(nèi)前面是加號(hào)的數(shù)不小于前面是減號(hào)的數(shù)這樣就有2種情況需要考察。然后，對(duì)于每一種動(dòng)物a,考察a的屬性在函數(shù)中前面的符號(hào)的情況，用0到2-1一個(gè)二進(jìn)制BN表示正負(fù)情況：如果BN的第i位為1，則前面的符號(hào)為正，令SIGN(BN,i)=1,否則為負(fù)，令SIGN(BN,i)=。定義表示正負(fù)情況為BN動(dòng)物a的值總和。則Friendliness的最大值為 其中ab,并且對(duì)于任意的i1,k,都有實(shí)現(xiàn)時(shí)，只要先枚舉a和 BN，然后查找滿足性質(zhì)并且值最大的b(ab)。這時(shí)的查找依懶于2棵第k層以maxF為元素、第1到第k-1層以線段樹為元素的線段樹。復(fù)雜度分析：每次查找和插入的時(shí)間復(fù)雜度都為O（logn），總的時(shí)間復(fù)雜度為O (n2logn),空間復(fù)雜度為O(n logn)，編程復(fù)雜度高。此時(shí)矛盾重重，時(shí)間復(fù)雜度依然很高，空間復(fù)雜度太大，編程復(fù)雜度令人難以忍受?！痉治雒堋坎浑y發(fā)現(xiàn)，產(chǎn)生這些矛盾的根本原因是性質(zhì)的要求太茍刻了。因此，此時(shí)須要放寬限制。【“放寬”方法化解矛盾】正所謂退一步海闊天空，試著放寬性質(zhì)的要求。嘗試將茍刻的要求去掉，但這樣編出來的程序和用原始算法編出來的程序的運(yùn)行結(jié)果是不正確的。因?yàn)檫@樣做實(shí)在太武斷了。先來對(duì)性質(zhì)做個(gè)詳細(xì)分析：注意到一個(gè)特殊性：越大，F(xiàn)riendliness的值越小，其余的（ik）越大，F(xiàn)riendliness的值越小。因此，試著把性質(zhì)放寬為只要保證 結(jié)果，這樣編出來的程序和用原始算法編出來的程序的運(yùn)行結(jié)果是完全一樣的。那么，這做法是否一定可以保證正確呢？下面的證明肯定了這一做法的正確性。證明：定理對(duì)于任意的A,BR,都有|A-B|A-B，|A-B|B-A。推論對(duì)于任意的A,B1,n，BN0,2-1都有滿足性質(zhì)的也就是滿足性質(zhì)的滿足性質(zhì)的設(shè)滿足性質(zhì)的(a,b,BN)所構(gòu)成的集合為S1,滿足性質(zhì)的所構(gòu)成的集合為S2，MAX1=MAX2=性質(zhì)包含性質(zhì)S1S2MAX1MAX2由推論可以得到：任意的（a,b,BN2）S2對(duì)應(yīng)的，都有一個(gè)(a,b,BN1) S1對(duì)應(yīng)的大于或等于這個(gè)值。MAX1MAX2MAX1=MAX2所以只要保證性質(zhì)，求出來的函數(shù)的最大值就是Friendliness的最大值。證畢。實(shí)現(xiàn)時(shí)，為了保證滿足性質(zhì)，只要先以為關(guān)鍵字將A從小到大排序，令為，這只要O (n2)的時(shí)間就可以把計(jì)算出來。然后，枚舉i和第k位為1的BN，以更新最大值。最后輸出最大值。復(fù)雜度分析：時(shí)間復(fù)雜度為O(nlogn+n2)。空間復(fù)雜度為O(n2)。到此，利用“放寬”方法已經(jīng)很好地解決了此題。【小結(jié)】歸納上面解