信息學(xué)集訓(xùn)隊(duì)作業(yè)boxes

1、IOI2003 中國(guó)國(guó)家集訓(xùn)隊(duì)難題活動(dòng)0018 解題金陵中學(xué)【題目大意】n 個(gè)盒子被放成一圈，每個(gè)盒子按順時(shí)針?biāo)泻凶永锴虻目倲?shù)不超過(guò)n。為 1 到 n，(1=n=1000)。每個(gè)盒子里都有一些球，且這些球要按如下的方式轉(zhuǎn)移：每一步可以將一個(gè)球從盒子中取出，放入一個(gè)相鄰的盒子中。目標(biāo)是使所有的盒子中球的個(gè)數(shù)都不超過(guò) 1。求達(dá)到目標(biāo)所需要的最少步數(shù)?！窘鉀Q情況】用貪心算法解決，其理論基礎(chǔ)是一個(gè)網(wǎng)絡(luò)流模型。時(shí)間復(fù)雜度是O(n2)，空間復(fù)雜度是O(n)?！舅惴ü８拧控澬乃惴?，每次安排一個(gè)球。安排每個(gè)球，都找出一個(gè)與初始局面相比差異最小的一個(gè)方案。安排好所有的球以后，最終局面與初始局面相比的差異，就是

2、最后的?！臼斋@與感謝】感謝林希德同學(xué)提醒，貪心算法實(shí)際上相當(dāng)與一個(gè)最小費(fèi)用最大流算法，使我找到了貪心算法的理論基礎(chǔ)。【正文】一、 網(wǎng)絡(luò)流模型在這個(gè)問(wèn)題的描述中，可以看到：目標(biāo)狀態(tài)中，所有的格子都只有 1 個(gè)球，而且要求總移動(dòng)次數(shù)最少。這似乎能用網(wǎng)絡(luò)流的模型來(lái)表示。的確是如此，可以建立一個(gè)源 S，匯 T，在 S 與所有的原來(lái)有球的盒子建立一條邊，容量為球的數(shù)量，費(fèi)用為 0；在所有的盒子和T 之間也建立一條邊，容量為 1，費(fèi)用也為 0；在相鄰的盒子之間分別建立邊，容量為，費(fèi)用為 1。最后，求出這個(gè)網(wǎng)絡(luò)的最小費(fèi)用最大流，費(fèi)用即是所要求的最少步數(shù)。上述模型的正確性是不容置疑的，但是，常規(guī)的最小費(fèi)用最大

3、流，時(shí)間復(fù)雜度都在O(n3)的級(jí)別上。題目描述中的N 最大可到 1000，不一定能夠承受。二、 基于網(wǎng)絡(luò)流模型的貪心算法正確的想法不能輕易放棄，還是一下網(wǎng)絡(luò)流在這道題目中的工作機(jī)理。按照最小費(fèi)用最大流的方法，每一次循環(huán)，都要將可行流增加 1，最終需要增加的次數(shù)就是球的總數(shù)。這恰好對(duì)應(yīng)于，依次安排每個(gè)球的移動(dòng)，直到它們都找到一個(gè)合適的存放點(diǎn)。在最初的幾次循環(huán)中，必然會(huì)產(chǎn)生形如 SBiT（Bi 指原先就有球的盒子）、費(fèi)用為 0 的增廣軌。這又對(duì)應(yīng)于，對(duì)于剛開(kāi)始就有球的盒子，一般都會(huì)在這個(gè)盒子中留下一個(gè)球（雖然這個(gè)球以后可能被移動(dòng)），那么這個(gè)球目前移動(dòng)的次數(shù)就是 0。最重要的就是在的時(shí)候，如圖 1（

4、加粗的弧是已經(jīng)滿載的弧，盒子與盒子之間的弧，如果有流量B1B1XB2YZXSB2TY圖 1Z則為綠色），目前已經(jīng)有 SB2，但是 B2T 已經(jīng)滿載，無(wú)法形成增廣軌。那么，網(wǎng)絡(luò)流算法是如何解決問(wèn)題的呢？這種情況其實(shí)就對(duì)應(yīng)于某個(gè)球在初始的位置與其它球形成了可以觀察到，這道題目的網(wǎng)絡(luò)流模型有兩個(gè)重要的性質(zhì)：。1所有滿足 PT 不滿載的頂點(diǎn) P，都沒(méi)有任何有流量的后向邊與之相連。確實(shí)如此，如果一個(gè)盒子中目前沒(méi)有擺放一個(gè)球，那么就必然沒(méi)有球移入這個(gè)盒子中。從任何一個(gè)盒子開(kāi)始，都不可能找到到達(dá) T 的負(fù)費(fèi)用路。這也是顯然的，在原來(lái)安排好所有球的基礎(chǔ)上，又增添一個(gè)球，只會(huì)帶來(lái)額外的調(diào)整費(fèi)用，不可能使總費(fèi)用降

5、低。2根據(jù)這個(gè)性質(zhì)， 可以得出：對(duì)于剛才的那種情況，只有 2 條增廣軌可能是最小費(fèi)用的增廣軌：分別沿著兩個(gè)方向不斷地尋找滿足 PT 不滿載的頂點(diǎn) P，沿途要盡量走后向邊（后向邊的費(fèi)用是-1），直至找到為止（因?yàn)椴淮嬖趶脑擖c(diǎn)到T 的負(fù)費(fèi)用路，所以繼續(xù)沿這個(gè)方向?qū)ふ业降脑鰪V軌費(fèi)用一定比現(xiàn)在高），所走的路線和PT 就可以形成一個(gè)增廣軌了。如圖 2 所示，藍(lán)色的弧組成了兩條增廣軌，費(fèi)用均為 2。B1B1XXSSB2TB2TYYZ圖 2得出了解決Z將這個(gè)理論對(duì)應(yīng)到實(shí)際的移球過(guò)程，的辦法：如果一個(gè)球在初始的位置和別的球形成了舊存在，就分別沿著順時(shí)針、逆時(shí)針的方向，將原來(lái)盒子中的球移出下一個(gè)盒子中，如果那個(gè)

6、盒子仍，就將該盒子中原來(lái)的球取出，沿著原方向繼續(xù)移動(dòng)，直至找到一個(gè)空盒子為止。那么，這個(gè)局面和初始時(shí)（所有球都集中在原來(lái)盒子友誼個(gè)球被移動(dòng)）的總的差異（也就是局面中每個(gè)球與初始位置的距離之和），就是形成這種局面的費(fèi)用，舍棄掉兩個(gè)局面中費(fèi)用較大的一個(gè)，如果費(fèi)用一樣大就隨便舍掉一個(gè)，兩種方案如圖 3 所示。這樣，就得到一個(gè)貪心算法：B1XB2YZB1XB2YZ圖 3初始時(shí)，所有的球都沒(méi)處理，所有的盒子中都沒(méi)有球。找到一個(gè)沒(méi)處理的球A，轉(zhuǎn) 3；如果找不到就計(jì)算目前局面與初始局面的差異，作為最終的費(fèi)用，結(jié)束。將球A 擺放在原來(lái)所處的位置上，如果該位置有球 B，則將球B 取出，轉(zhuǎn) 4。將球B 放入順時(shí)針

7、方向相鄰的盒子里，如果該盒子里有球 C，則將球 C 取出放入順時(shí)針?lè)较蛳噜彽暮凶永锶绱搜h(huán)往復(fù)，直至找到一個(gè)沒(méi)有球的盒子。計(jì)算費(fèi)用，將局面恢復(fù)為沒(méi)有移動(dòng)球 B 的狀態(tài)。將球B 放入逆時(shí)針?lè)畔蛳噜彽暮凶永铮绻摵凶永镉星?C，則將球 C 取出放入逆時(shí)針?lè)较蛳噜彽暮凶永锶绱搜h(huán)往復(fù)，直至找到一個(gè)沒(méi)有球的盒子。計(jì)算費(fèi)用，將局面恢復(fù)為沒(méi)有移動(dòng)球B 的狀態(tài)。123456取兩種移動(dòng)方案中費(fèi)用較小的一種進(jìn)行移動(dòng)，完成A 的擺放和的調(diào)整。這個(gè)貪心算法比起網(wǎng)絡(luò)流算法，更容易理解，而且它和原來(lái)的網(wǎng)絡(luò)流算法從本質(zhì)上說(shuō)是完全一致的，因此它的正確性也得到了充分的保證。三、 復(fù)雜度分析每擺放一個(gè)球，如果要解決，那么在一個(gè)方向上最多要進(jìn)行 n-1 次操作（否則就找不到?jīng)]有球的盒子了），一次計(jì)算費(fèi)用也最多只要進(jìn)行 n 次減法。因?yàn)樽疃嘈枰獢[放 n 個(gè)球，所以，總的時(shí)間復(fù)雜度是O(n2)，