學(xué)校題目08年省選賽講義

1、Promotion 解題問(wèn)題描述這道題目讓按一定規(guī)則，模擬一個(gè)促銷活動(dòng)，并統(tǒng)計(jì)所需的費(fèi)用。問(wèn)題分析先做一些約定：整個(gè)促銷活動(dòng)持續(xù)了n 天，n5000第i 天放入的鈔票有 ai張，ai105，且 s=ai106第i 天放入的鈔票面值分別是bi1, bi2, , biai，bij1063.定義一個(gè)線性表D，它可以支持如下操作：1.2.3.4.5.將表D 清空：D.init在表D 中加入一個(gè)數(shù)字x：D.add(x)從表D 中刪除一個(gè)數(shù)字x：D.remove(x)求表D 中的最小數(shù)：D.getmin求表D 中的最大數(shù)：D.getmax于是，這道題目的算法可以簡(jiǎn)單的描述如下：由此可見(jiàn)，算法描述并不復(fù)雜，

2、關(guān)鍵是數(shù)據(jù)結(jié)構(gòu)的選擇。的這個(gè)算法當(dāng)中，對(duì)每種操作各做了多少次：先看一下上面操作次數(shù)init1add(x)s=ai106remove(x)2n104getminn5000getmaxn5000ans := 0; /計(jì)數(shù)器清零D.init; /表初始化for i := 1 to n do /順次處理每一天的促銷活動(dòng)for j := 1 to ai do /順次處理第i 天的鈔票D.add(biai); /在表中加入這個(gè)面額min := D.getmin; /求表中的最小值max := D.getmax; /求表中的最大值ans := ans + max min; /更新計(jì)數(shù)器D.remove(mi

3、n); /從表中刪除最小值D.remove(max); /從表中刪除最大值輸出ans下面，著重幾種不同的數(shù)據(jù)結(jié)構(gòu)和它們的效率。1. 采用普通的線性表采用普通的線性表，則線性表的長(zhǎng)度不超過(guò) s，各操作的時(shí)間復(fù)雜度如下表：由此可以看出，采用普通的線性表，則時(shí)間復(fù)雜度為 O(ns)，太大了。2. 采用二叉堆由于表D 即要求最大值，又要最小值。因此，需要一個(gè)小根堆和一個(gè)大根堆。同樣，堆的長(zhǎng)度不超過(guò)s，各操作的時(shí)間復(fù)雜度如下表：由此可見(jiàn)，采用二叉堆，時(shí)間復(fù)雜度為 O(n+s)logs)，基本上可以承受。二叉堆的空間復(fù)雜度也是 O(s)。顯然，在 BP 下無(wú)法承受。但注意到，因?yàn)檎麄€(gè)活動(dòng)不超過(guò) 5000

4、天，如果有一天 ai=105，那么把那天的鈔票按面值排序，則只有面值最小的 5000 張和最大的 5000 張可能對(duì)顯然都可以拋棄。有用，而其它的一般的只需要保存面值最小的n 張和最大的n 張鈔票就可以了。這樣，算法的空間復(fù)雜度就降到了 O(n)，而時(shí)間復(fù)雜度也就進(jìn)一步降到了 O(n+s)logn)。不過(guò)二叉堆的操作卻比較復(fù)雜?，F(xiàn)在大家都用 windows/linux 了，640K 的內(nèi)存限制已不復(fù)存在。如果允許大內(nèi)存，有沒(méi)有更快更簡(jiǎn)單的實(shí)現(xiàn)方法呢？是肯定的。注意到下面兩點(diǎn)：a. 第一種數(shù)據(jù)結(jié)構(gòu)，它耗時(shí)主要在操作getmax 和getmin 上1bij106b.第一點(diǎn)說(shuō)明關(guān)鍵在于優(yōu)化操作 ge

5、tmax 和 getmin；第二點(diǎn)提示數(shù)組來(lái)實(shí)現(xiàn)表D。采用標(biāo)志3. 采用簡(jiǎn)單的標(biāo)志數(shù)組定義dx，表示數(shù) x 在表D 中出現(xiàn)的次數(shù)。因?yàn)?x 在1, 106區(qū)間內(nèi)，令操作次數(shù)時(shí)間復(fù)雜度init1O(s)add(x)s=ai106O(logs)remove(x)2n104O(logs)getminn5000O(1)getmaxn5000O(1)操作次數(shù)時(shí)間復(fù)雜度init1O(s)add(x)s=ai106O(1)remove(x)2n104O(1)getminn5000O(s)getmaxn5000O(s)m=106，則標(biāo)志數(shù)組各項(xiàng)操作的時(shí)間復(fù)雜度是：很遺憾，這樣做算法的時(shí)間復(fù)雜度還是高達(dá) O(s

6、+nm)。但如果 把數(shù)組 d分段，比如每段長(zhǎng)為L(zhǎng)，再令一個(gè)數(shù)組 c，ci表示在區(qū)間(i-1)L+1, iL中的數(shù)在表 D 中出現(xiàn)的次數(shù)，則在找最小最大值的時(shí)候，可以分兩步走：先在 c 數(shù)組中找到最小（或最大）的i，使得ci0，然后再在區(qū)間(i-1)L+1, iL中，從d 數(shù)組中找到具體的那個(gè)數(shù)。如果 令L=m1/2，則找最小最大值的復(fù)雜度可以降到O(m1/2)。于是引出新的數(shù)據(jù)結(jié)構(gòu)：分段標(biāo)志數(shù)組。4. 采用分段標(biāo)志數(shù)組定義dx，表示數(shù) x 在表D 中出現(xiàn)的次數(shù)。其中 x 屬于區(qū)間1, m。令 L= m1/2，定義ci表示在區(qū)間(i-1)L+1, iL中的數(shù)在表D 中出現(xiàn)的次數(shù)。這個(gè)數(shù)據(jù)結(jié)構(gòu)各項(xiàng)

7、操作的時(shí)間復(fù)雜度是這個(gè)算法的時(shí)間復(fù)雜度是 O(s+nm1/2)，對(duì)于題目給出的數(shù)據(jù)范圍，該算法的時(shí)間復(fù)雜度要比采用二叉堆的算法 2 還要低。程序也很容易實(shí)現(xiàn)，唯一的是空間復(fù)雜度是 O(m)，超過(guò)了 BP 可以處理的范圍，當(dāng)然，用fp 就可以了。就小結(jié)“程序=算法+數(shù)據(jù)結(jié)構(gòu)”，這道題目的很好的驗(yàn)證了這一點(diǎn)：它的算法描述相當(dāng)簡(jiǎn)明，關(guān)鍵就在于數(shù)據(jù)結(jié)構(gòu)的選擇。問(wèn)題分析中，提到了兩個(gè)可行的數(shù)據(jù)結(jié)構(gòu)：一是采用二叉堆，二是采用“分段標(biāo)志數(shù)組”。其中二叉堆空間需求小，而標(biāo)志數(shù)組時(shí)間復(fù)雜度低，兩種方法適用于不同的編程環(huán)境。參考程序采用的是二叉堆（算法 2）。操作次數(shù)時(shí)間復(fù)雜度描述init1O(m)d, c 清零add(x)s=ai106O(1)inc(dx);inc(cx div L);remove(x)2n104O(1)dec(dx);dec(cx div L);getminn5000O(m1/2)分兩步查找，先c 后dgetmaxn5000O(m1/2)分兩步查找，先c 后d操作次數(shù)時(shí)間復(fù)雜度描述