第二部分sequence解題報告

1、第4頁共4頁Baltic Olympiad in Informatics 2004Sequence解題報告華東師范大學(xué)第二附屬中學(xué) 吳佳俊【時空限制】每個測試點時間限制3秒，空間限制64M?！締栴}描述】給定一個序列t(1), t(2), ., t(N)，要求你求一個遞增序列z(1) z(2) . 每次處理一個數(shù)時，先把它看成單獨的一段，然后如果前一段的值比它小，則兩段合并，新值為兩段的中位數(shù)。反復(fù)操作，直至序列合法。這樣顯然合并最多n次。數(shù)據(jù)結(jié)構(gòu)如果選用二叉搜索樹，每次采用啟發(fā)式合并，復(fù)雜度為O(nlog2n)有一個巧妙的優(yōu)化，每次插入的時候，不要直接插到最后。對于數(shù)k，找到某一段p，滿足kv

2、alp且kvalp-1，然后把k插入段p中。當(dāng)然，仍然把最后一段的大小加1，而不是把段p的大小加1。這樣做的理由是，在之前的算法中，如果k要被刪除，那么段p起所有段必然已經(jīng)全部被合并，因此不妨直接將k插入段p另一個O(nlogn)的算法是使用可合并堆，思路和前面相同，可合并堆的介紹這里略去?！舅惴枋觥棵看翁幚硪粋€數(shù)時，先把它看成單獨的一段，然后如果前一段的值比它小，則兩段合并，新值為兩段的中位數(shù)。反復(fù)操作，直至序列合法。這樣顯然合并最多n次?？紤]到每個段的中位數(shù)不可能增大，每個段可以用一個最大堆來維護，保存當(dāng)前段中的一半的元素，則堆頂即為中位數(shù)。每次插入的時候，不要直接插到最后。對于數(shù)k，找

3、到某一段p，滿足kvalp且kvalp-1，然后把k插入段p中。當(dāng)然，仍然把最后一段的大小加1【其他算法】還有一種基于分治思想的O(nlogn)的做法。為了說明這個算法，首先要證明一個引理：最小的滿足zix的i是最小的滿足對任意ijn，ti,ti+1,tj的中位數(shù)都比x大的i?？梢院唵蔚赜弥暗暮喜⒍蔚乃惴▉碜C明：用反證法，如果存在一個j使得條件不滿足，那么在用之前算法的時候，i所在的段就會在處理到j(luò)的時候中位數(shù)小于由此可以設(shè)計出一個分治算法，用(i,j,low,high)表示從i到j(luò)的目標(biāo)段中所有值在low,high范圍內(nèi)時，所需費用的最小值。令x=(low+high)/2，則只需快速找到劃

4、分點i即可。下面是一個O(n)找到i的辦法，對每個i記錄fi表示mintot_greateri,j-tot_smalleri,j，其中ijn，tot_greateri,j表示i到j(luò)里有多少個數(shù)大于x，反之亦然。fi的值可以由【實現(xiàn)情況】seq.pas實現(xiàn)了優(yōu)化后不必合并的二叉堆算法。【感謝】完成題解過程中參考了另一份英文的題解，只是不知出處?！靖戒洝吭}SequenceShort formulation. The number sequence is given. Your task is to construct the increasing sequence that approximat

5、es the given one in the best way. The best approximating sequence is the sequence with the least total deviation from the given sequence. More precisely. Let t1, t2, , tN is the given number sequence. Your task is to construct the increasing number sequence z1 z2 zN .The sum |t1 - z1| + |t2 - z2| +

6、+ |tN - zN| should be a minimal feasible. Input There is the integer N (1N1000000) in the first line of input file seq.in. Each of the next N lines contains single integer the given sequence element. There is tK in the (K+1)-th line. Any element is satisfying to relation 0tK2000000000. Output The first line of output file seq.out must contain the single integer the minimal possible total deviation. Each of the next N lines must contain single integer the recurrent element of the best approximating sequence. If there are several solutions, your program must output a