梅詩珂ioi2009作業(yè)izbori解題報告

1、izbori(Croatian OI)解題報告 安徽省合肥一中 梅詩珂 題目大意：有N個政黨爭奪M個議席，議席分配規(guī)則如下：首先把所有得票嚴(yán)格小于總票數(shù)5%的政黨除去,設(shè)第i個政黨得到ai張選表，當(dāng)前已得到了seati個議席，那么當(dāng)前議席將分配給最大的政黨，如果有多個，則分配給編號最小的政黨?，F(xiàn)在已經(jīng)統(tǒng)計出一些選表，并且總共有V個選民參加投票。問對每個政黨，其最終最多得到的議席數(shù)與最少得到的議席數(shù)。約束條件： 1N100 , 1M100 , 1V10000000分析：每個政黨最多得到的議席數(shù)很容易求，只要讓未確定選票全部為該政黨得到即可。下面我們考慮最少議席的求法。顯然如果某政黨當(dāng)前票數(shù)小于總

2、票數(shù)的5%，則最少得0票。最小情況下，剩余票數(shù)一定全分給其他政黨，我們考慮剩余選票分配方案，發(fā)現(xiàn)難以下手的地方在于議席分配規(guī)則，每個政黨是互相影響的，要解決問題，就必須發(fā)現(xiàn)規(guī)則的有用性質(zhì)。聯(lián)系實(shí)際生活，分配議席一般是按得票比例，這里應(yīng)該也是如此。經(jīng)過簡單觀察，我們得到如下性質(zhì)。性質(zhì)1：設(shè)最后一個議席由政黨v得到，此時第i個政黨得到了seati個議席，當(dāng)且僅當(dāng) 且，這里設(shè)。 證明：必要性。如果對某個iv的情況同理。充分性。如果最后一個議席不由v得到，那么設(shè)由p得到，如果pi,那么與矛盾。這個性質(zhì)說明對政黨v，設(shè)其得到了seatv個議席，我們算出對應(yīng)的符合條件的seati(iv)，當(dāng)且僅當(dāng)時，v的

3、議席數(shù)能達(dá)到。很顯然，如果seatv個議席能得到，那么所有比seatv小的議席數(shù)都能達(dá)到，我們可以二分v需要達(dá)到的議席數(shù)seatv，對固定的seatv我們要分配不超過剩余選票數(shù)的選票給一些政黨，使,這是很明顯的動態(tài)規(guī)劃問題。對給定的seatv,我們設(shè)Needi,j為對于i(iv)政黨，要使其擁有j個議席，至少還要分配的票數(shù)，根據(jù)上述性質(zhì)，我們有 其中表示一個很小的實(shí)數(shù)，為的是保證，在實(shí)踐中可取。Max括號中的第2項(xiàng)是保證其票數(shù)不小于總票數(shù)的5%。有了Need，我們設(shè)表示前i個政黨分得j個議席最少需要的剩余選票數(shù)，則 如果計算過程中發(fā)現(xiàn)不超過剩余票數(shù)，則v政黨最少得不到seatv個議席，否則能得

4、到。 分析算法時間復(fù)雜度，我們要枚舉所有已得票不少于總票數(shù)5%的政黨，設(shè)共有d個，二分枚舉其最少票數(shù)，對每個最少票數(shù)的判斷中Need與f狀態(tài)都是，f的轉(zhuǎn)移,故判斷復(fù)雜度為，總復(fù)雜度。在實(shí)踐中該算法以足夠通過所有測試數(shù)據(jù)，但本算法還可以優(yōu)化。優(yōu)化：我們只考慮Needi,j的公式Max中第一項(xiàng)，為了方便，我們只考慮iv的情況類似)。我們看到，該項(xiàng)只是在上加了一個向上取整號。如果沒有這個符號，那么由于av,seatv都是常數(shù)，我們設(shè)Hi,j表示這時的最優(yōu)值，也即為了處理向上取整號，我們需要如下性質(zhì)。性質(zhì)2：如果,其中A,B為整數(shù)，則。證明：如果x,y都是整數(shù)，則,否則，得到。有了性質(zhì)2，我們知道使Hi,j最小的k也就是使fi,j最小的k，而使Hi,j最小的k是可以再Hi,j求解過程中順便求得的?，F(xiàn)在再考慮Max中后面兩項(xiàng)，由于是遞增的，所以Needi,j中,對固定的i，隨著j增加，Needi,j出現(xiàn)的值依次為。在Needi,j中出現(xiàn)一定是一個區(qū)間，那么可以用2個單調(diào)隊(duì)列維護(hù)。分析總復(fù)雜度，H的求解是的，單調(diào)隊(duì)列對固定的i，j掃一遍是的，故總復(fù)雜度為?？偨Y(jié)：回顧解題過程，我們首先對議席分配規(guī)則進(jìn)行分析，從而把問題轉(zhuǎn)化成對每個政黨求座位數(shù)，消除了政黨之間的互相聯(lián)系，從而獲得了動態(tài)規(guī)劃算法。而后，我們又對f數(shù)組的轉(zhuǎn)移