《爺爺?shù)牧P金》解題報告

《爺爺?shù)牧P金》解題報告Bysx349【問題描述】小Y的爺爺老Y是一個有名的鞋匠。老Y人很厚道，雖然年紀(jì)大了，但是工作還是很忙的，定單很多，以前很多手工計算的活都越來越難以完成，經(jīng)常陪錢。小Y看在眼里急在心里，他想幫助爺爺做點(diǎn)事，當(dāng)然是利用他的特長——計算機(jī)編程。他分析后發(fā)現(xiàn)爺爺有n個必須完成的訂單，一天只能處理一個訂單，但是一個訂單可能需要很多天才能完成。對于第i個訂單，整數(shù)Ti(1≤Ti≤1000)代表爺爺完成這件工作所需要的天數(shù)。但是，訂單太多是需要付出代價的，每個客戶都認(rèn)為自己的訂單應(yīng)該被馬上處理。因此對于第i件工作，在開始著手這件工作之前每天都要付罰金Si(1≤Si≤10000)?，F(xiàn)在，小Y想編一個程序來幫助爺爺找出所付罰金最少的訂單處理次序?！据斎胛募浚╯hoemaker.in）輸入文件第一行給出訂單的總數(shù)n(1≤n≤1000)。接下來n行，第i行有兩個整數(shù)，即完成第i件工作所需時間Ti和延遲這項(xiàng)工作每天需要交的罰金Si?！据敵鑫募浚╯hoemaker.out）輸出文件只有一行一個整數(shù)，即最少的罰金。【輸入輸出樣例】shoemaker.inshoemaker.out43411000225542【問題分析】不妨先考慮這道題的一個簡化版本——排隊(duì)打水問題：有N個人正在排隊(duì)打水，其中第i個人打水所用的時間為。請安排這些人打水的順序，使得每個人等待的時間的總和，即最小。對比排隊(duì)打水問題和當(dāng)前的問題可以發(fā)現(xiàn)，其實(shí)排隊(duì)打水問題是當(dāng)前問題在S均為1的情況下的一個特例。如何解答排隊(duì)打水問題？考慮將上述式子展開得到：也就是說，排在越前面的人，他所用的打水時間就越多次成為后面的人的等待時間。因此，應(yīng)該盡量將打水時間短的人放在隊(duì)伍的前列。用數(shù)學(xué)語言來表達(dá)這個想法：不妨考慮打水隊(duì)伍中的兩個人i與j（i<j）。如果他們的打水時間，那么必然可以交換這兩個人，使得打水等待總時間變短。不妨設(shè)交換前的總時間為，而交換后的總時間為，那么有：因此，只要當(dāng)前的打水隊(duì)伍中存在滿足上述條件的兩個人，就必然可以進(jìn)行一次調(diào)整，最終得到的序列，必然是一個按照打水時間不降序的隊(duì)伍。接下來，回過頭看《爺爺?shù)牧P金》這道題。所有的S均為1的特例已經(jīng)解決了，那么，能不能由此借鑒出該題的做法呢？由于S不為1，因此，現(xiàn)在要做的，是使得最小。一個最基礎(chǔ)的想法是，依然盡可能的讓時間短的訂單排在序列的前列。顯然，由于現(xiàn)在的式子結(jié)果與S有關(guān)，因此在同樣按上述推理時必然會因?yàn)镾的不同而導(dǎo)致結(jié)果不定（與的大小關(guān)系不定）。更進(jìn)一步的想法是，既然這個式子與S和T均有關(guān)，不妨考慮每份訂單的“性價比”，即。如果將一份訂單拆成份T值均為的訂單，拆分過后的每一個新“訂單”的S值均為1，原問題就轉(zhuǎn)化成了排隊(duì)打水問題。得出最終的序列后，根據(jù)上面的分析，同一份訂單拆分出的新“訂單”一定可以安排在連續(xù)的位置，再將這些訂單合并，問題又恢復(fù)到了當(dāng)前問題。如果省略兩個問題互相轉(zhuǎn)化的那一步，可以發(fā)現(xiàn)，其實(shí)最后的排列順序一定是按照不降序的。但是在將兩個問題轉(zhuǎn)化的過程中，由于訂單的拆分，會出現(xiàn)一部分新“訂單”，因?yàn)榈却瑢儆谝环菰唵蔚钠渌隆坝唵巍?，而使得罰金增加的情況，從而使得在原問題轉(zhuǎn)化為排隊(duì)打水問題的過程中，總的“等待時間”增加了。但是，由于無論這些新“訂單”在排隊(duì)打水序列中的位置如何，增加的總時間總為，因此所有的排隊(duì)打水序列修正合并為訂單序列后，最優(yōu)的排隊(duì)打水序列依然會是最優(yōu)的訂單序列。同樣的，也可以給出一個基于調(diào)整交換的證明。不妨假設(shè)當(dāng)前已經(jīng)存在一個訂單序列（不一定是最優(yōu)的）：考慮其中的兩個訂單和，假設(shè)交換這兩個訂單前后總的罰金為和:可以發(fā)現(xiàn)，展開之后，第一項(xiàng)和第四項(xiàng)的值在交換前后不發(fā)生改變，同樣不發(fā)生改變的還有一項(xiàng)。不妨令：那么，可以得到：當(dāng)且僅當(dāng)時，應(yīng)當(dāng)交換這兩份訂單使得總罰金減小，因此：由此可以得出結(jié)論：如果序列當(dāng)中任意相鄰的兩項(xiàng)滿足，那么就一定可以通過交換這兩份訂單使得總罰金減小。而如果任意相鄰的兩項(xiàng)滿足，那么任意交換這兩個訂單不會影響總罰金的大小。根據(jù)這個結(jié)論，再利用一下反證法：顯然，最優(yōu)序列一定是存在的；假設(shè)最優(yōu)序列中存在相鄰的兩項(xiàng)的遞減，那么一定可以將它們交換使得總罰金減小形成更優(yōu)的序列，與當(dāng)前序列即為最優(yōu)序列矛盾。所以最優(yōu)訂單序列中相鄰的兩項(xiàng)的一定是不降的，而整個最優(yōu)訂單序列一定是關(guān)于不降的一個序列。【算法實(shí)現(xiàn)】根據(jù)以上結(jié)論，可以得到一個頗為簡單的算法：讀入S與T之后，按照從小到大排序，然后逐個計算罰金即可。在大小比較時，為了避免實(shí)數(shù)比較的一些問題，可以將不等式兩邊通分轉(zhuǎn)化為整數(shù)比較。時間復(fù)雜度：空間復(fù)雜度：【心得體會】（淺談有關(guān)貪心策略的選擇和對其證明的必要性）本題最終化歸為一個簡單明確的貪心結(jié)論，其思考過程就如同行文所述，是從排隊(duì)打水問題之中獲得的靈感。但在實(shí)戰(zhàn)的過程中，有很多同學(xué)只是直接利用了這個結(jié)論，而并沒有考慮去證明它的正確性。在信息學(xué)競賽中，這確實(shí)是一個值得注意的地方。由于貪心算法往往十分簡單，時間復(fù)雜度、編程復(fù)雜度在一定程度上都顯著優(yōu)于同樣用于解決最優(yōu)化問題的動態(tài)規(guī)劃、搜索等其他算法，而且其可靠程度往往并不低，因此經(jīng)常受到選手的青睞。但是，貪心算法的一個致命軟肋就在于，一旦不能證明貪心算法的正確性，比如貪心算法本身是錯誤的只是湊巧在幾個點(diǎn)上與數(shù)據(jù)相符，或者某種貪心策略只適用于某些有規(guī)律的特殊情形，又或者貪心算法只能保證得到較優(yōu)值而非最優(yōu)值，那么在比賽的過程中是采用這種貪心算法，還是選擇其他算法，就是選手對于時間、成績的一個博弈；退一步說，如果我們現(xiàn)在面對一個貪心算法能夠解決我們面臨的一部分小數(shù)據(jù)或特殊數(shù)據(jù)，我們是否應(yīng)該花一點(diǎn)時間（這“一點(diǎn)時間”可長可短）去證明這個貪心算法的正確性，同樣也是一個對于時間的博弈?？偟膩碚f，貪心算法適用的情況，一種是貪心算法本身就是問題的正確解法：這種情況下，是必須要花一點(diǎn)時間證明這個正確性的；另一種是隨機(jī)化貪心構(gòu)造或選擇，通過多次不同決策得到多個較優(yōu)值而取得最優(yōu)值的做法：這種情況下，往往并不一定要保證貪心算法的正確性；但是，在面對一道題目時，貪心算法是否就是我們當(dāng)前應(yīng)該尋找的一種算法，依舊需要我們有清晰的大腦和豐富的經(jīng)驗(yàn)來進(jìn)行甄別，并不是一朝一夕就能練成，也不是三言兩語就能講清的?！綪ascal參考程序】//Program:爺爺?shù)牧P金//PROG:shoemaker//LANG:PASCALProgramShoeMaker;Var N,I,Time,Ans:Longint; S,T:Array[0..1000]ofLongint; ProcedureSwap(A,B:Longint); Var TT:Longint; Begin TT:=S[A];S[A]:=S[B];S[B]:=TT; TT:=T[A];T[A]:=T[B];T[B]:=TT; End; ProcedureSort(L,R:Longint); Var I,J,MidS,MidT:Longint; Begin I:=L;J:=R;MidS:=S[(I+J)Div2];MidT:=T[(I+J)Div2]; Repeat WhileS[I]*MidT>T[I]*MidSdoInc(I); WhileS[J]*MidT<T[J]*MidSdoDec(J); IfI<=JThenBegin Swap(I,J); Inc(I);Dec(J); End; UntilI>J; IfL<JThenSort(L,J); IfI<RThenSort(I,R); End;Begin Assign(Input,'shoemaker.in');Assign(Output,'shoemaker.out');Reset(Input);Rewrite(Output);Read(N); ForI:=1to