學校題目08年省選賽講義

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

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

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

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

5、tmax 和 getmin；第二點提示數組來實現表D。采用標志3. 采用簡單的標志數組定義dx，表示數 x 在表D 中出現的次數。因為 x 在1, 106區(qū)間內，令操作次數時間復雜度init1O(s)add(x)s=ai106O(logs)remove(x)2n104O(logs)getminn5000O(1)getmaxn5000O(1)操作次數時間復雜度init1O(s)add(x)s=ai106O(1)remove(x)2n104O(1)getminn5000O(s)getmaxn5000O(s)m=106，則標志數組各項操作的時間復雜度是：很遺憾，這樣做算法的時間復雜度還是高達 O(s

6、+nm)。但如果 把數組 d分段，比如每段長為L，再令一個數組 c，ci表示在區(qū)間(i-1)L+1, iL中的數在表 D 中出現的次數，則在找最小最大值的時候，可以分兩步走：先在 c 數組中找到最?。ɑ蜃畲螅┑膇，使得ci0，然后再在區(qū)間(i-1)L+1, iL中，從d 數組中找到具體的那個數。如果 令L=m1/2，則找最小最大值的復雜度可以降到O(m1/2)。于是引出新的數據結構：分段標志數組。4. 采用分段標志數組定義dx，表示數 x 在表D 中出現的次數。其中 x 屬于區(qū)間1, m。令 L= m1/2，定義ci表示在區(qū)間(i-1)L+1, iL中的數在表D 中出現的次數。這個數據結構各項

7、操作的時間復雜度是這個算法的時間復雜度是 O(s+nm1/2)，對于題目給出的數據范圍，該算法的時間復雜度要比采用二叉堆的算法 2 還要低。程序也很容易實現，唯一的是空間復雜度是 O(m)，超過了 BP 可以處理的范圍，當然，用fp 就可以了。就小結“程序=算法+數據結構”，這道題目的很好的驗證了這一點：它的算法描述相當簡明，關鍵就在于數據結構的選擇。問題分析中，提到了兩個可行的數據結構：一是采用二叉堆，二是采用“分段標志數組”。其中二叉堆空間需求小，而標志數組時間復雜度低，兩種方法適用于不同的編程環(huán)境。參考程序采用的是二叉堆（算法 2）。操作次數時間復雜度描述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操作次數時間復雜度描述