第三章心nTin個n個人的平均等待時間最小。n1n 3271991000234335599 totalT1(T1T2totalnT1(n1)T2k1k2,k3,…kn，當(dāng)Tk1≤Tk2Tk3Tkn時，total取到最小值。如何證明呢？方法如下：因為totalnTk1(n1)Ti<j，而TkiTkjtotal1kikjtotaltotal2 (ni (nj1)T((ni1)T(nj (ni T)(nj (j T riddle.???（pas,c, 人為了表彰大家的勇氣，先每個參賽者m元。先不要太高興！因為這些錢還不一定都是你的？！接下來宣布了比賽規(guī)則：。，規(guī)定期限ti前完成(1≤ti≤n)。如果一個游戲沒能在規(guī)定期限前完成，則要從費m元中wi，wi為自然數(shù)，不同的游戲扣去的錢是不一樣的。當(dāng)然，每個游戲本身都很簡單，保證每個參賽者都能在一個時段內(nèi)完成，而且都必須從整時段開始只是想考考每個參賽者如何安排組織自己做游戲的順序。作為參賽者很想贏得冠軍，當(dāng)然更。，輸入文件riddle.in4第1行為m，表示一開始給每位參賽者的錢；2n，表示有n個小游戲；3n1n4n1n輸出文件riddle.out，僅1行。表示能贏取最多的錢 7424

3020k，我們應(yīng)該把它安排在哪個時段完成呢?k個時段，因為放1～k任意一個位置，效果都是一樣的。一旦出現(xiàn)一個不可能在規(guī)定時限前完成的任務(wù)，1。n個時段，發(fā)現(xiàn)里面所分配的任務(wù)的結(jié)束時間等于n-1，那么就說明1～nn個時段，挑出一個最小的去掉并2。match.???（pas,c,kkn1，n2，…，nkkini；接例如：k＝2，n1＝n2＝2，A代表你，P代表計算機，若決定A P：(1,0) {P勝利AA：(2,0) {A勝利A已將游戲歸結(jié)為(2,2)P如何取Alose1 4 {3436 36 2 152219kninnn個二進制數(shù)按位相加(不進行進位)n個非負(fù)整數(shù)的狀態(tài)為偶狀態(tài)，從向低位尋找到第一位按位加之和為奇數(shù)的二進制位，設(shè)這一位為第k位，則n個數(shù)的k1k0，則所kk位低的所有位作0110，這樣就構(gòu)造出了一個偶狀態(tài)，并且被改變的那個數(shù)一定變小了因為這個數(shù)被改變的所有二進制位中的最從10。n＝3三堆火柴棒的數(shù)量分別為3，6，93＝(0011)2，6＝(0110)2，9＝(1001)2，最之和為1，其中9對應(yīng)的二進制數(shù)的最為1，將其變?yōu)?，次之和也是1，9n16個元素的數(shù)組（線性表）b[i,0]i個數(shù)的最低位，n個數(shù)的狀01來表示，0表示偶，1表示奇。最后的狀態(tài)(0)為偶狀態(tài)，所以開始狀態(tài)為偶狀態(tài)時，大家都知道國際象棋特級大師與IBM公司研制的“深藍”超級計算機進行國際prod.???（pas,c,ABiA、BAi、Bin個產(chǎn)品的加工順A、B兩車間加工完畢的時間。nn個產(chǎn)品在A車間加工各自所要的時間(都是整數(shù))。nnB車間加工各自所要的時間(都是整數(shù))358762141542AA車間加工時，B車間是B車間加工時，A車間已經(jīng)完成了任務(wù)。ABB車間加工時間最短的產(chǎn)品放在最后加工，這樣使A車間的空閑時間最少。Mi＝min{Ai，Bi}MMi=Ai，則將它安排在Mi＝Bi，則將它安排在從尾開始的已安排的生B車間還在加工其他產(chǎn)品，tBA車間加工過的產(chǎn)品。在這樣的條件S中任務(wù)所要的最短時間T(St)=min{Ai+T(s-{Ji}，Bi+max{t-Ai0})}，其中，Ji∈3-1iAB圖3- A等B的情3-2iBA圖3- B等A的情T(S,t)AiT(s{Ji},Bimax{tAiAiAjT(S{Ji,Jj},Bjmax{Bimax{tAi,0}AjAiAjT(S{Ji,Jj},TijTijBjmax{Bimax{tAi,0}AjBjBiAjmax{max{tAi,0},AjBiBjBiAjmax{tAi,AjBiBjBiAiAjmax{t,Ai,AiAjBi如果max{tAiAiAjBit，則TijtBiBjAi如果max{tAiAiAjBiAi，則TijBiBj如果max{tAiAiAjBiAiAjBi，則TijBjJiJjT'(S,t)AiAjT(S(Ji,Jj),Tji其中TijBiBjAiAjmax{tAjAiAjBj按照上面的假設(shè)，有T<=T’max{t,AiAjBi,Ai}max{t,AiAjBj,AjAiAjmax{Bi,Aj}AiAjmax{Bj,AimaxBjAimaxBiAjJohnsonJiJj之前可以得到最優(yōu)解。也就是在A車間加工時間短的安排面，在B車間加工時間短的任務(wù)（A1,A2,A3,A4,A5）=（3,5,8,7,（B1,B2,B3,B4,B5）=（6,2,1,4,則（m1,m2,m3,m4,m5）=（3,2,1,4,9）（m3,m2,m1,m4,m5）（2，3（1，2，3（14，2，3m5m5=B5m5安排在后面（1，5，4，2，3maxmul.???（pas,c,n分解成若干個互不相同的自然數(shù)的和，且使這些自 23n10000，n52662873833na1,a2,a3,a4,…,am這m2開始的一串a(chǎn)11n減少，沒有實際意義，只n3、4時才可能用上。h。證明如下：h分為兩部分：a，h-a2<＝a<h/2a*(h-a)。h>2*a，所以a*(h-a)-h>2*a*(a-1)-a*a=a*a-2*a=a*(a-又因為a>＝2，所以a*(a-2)>=0a*(h-a)-h>Oa*(h-a)>h5，將它拆分為不同的部分后na1+a2+a3+a4+…+am，n時，a12，a23，…，am-1m2開始按照自然數(shù)amm-1個數(shù)。為什么要從后面開始往前呢?同樣是考慮數(shù)3出現(xiàn)了重復(fù)。這樣操作到底是否正確、是否能保證乘積最大呢?還要加以證明。2b＝s+2，a*b＝(s-2)*(s+2)＝s2-4。a-b的絕對值越小，乘積的常數(shù)大，即乘積越大，上面的序列a1,a2,a3,a4,…,am正好1，21，323。n=10為例，先拆分為：10=2+3+4+114小，將其分配給前面的一項，10=2+3+52*3*5＝30。以n=2020=2+3+4+5+6，正好是連續(xù)自然數(shù)的和，所以最大乘積為以將其平均分給前面的項，優(yōu)先考慮后面的項，即前面的4項各分到1，笫56分到2，26＝3+4+5+6+83*4*5*6*8＝2880。a2；n>a時做選擇an減少a；如果n>0n從最后一項開始平均分給各項；如果n0，再從最后一項開始分一次；trees.???（pas,c,種些樹并指定了三個號碼B，E，T。這三個數(shù)表示該居民想在B和E之間最少種T棵樹。trees.inN，區(qū)域的個數(shù)(0<N≤30000)；第二行包含H，房子的數(shù)目(0<H≤5000)； 48935O(h)，更新需要的時間為O(n)O(n*h)napkin.???（pas,c,NiRi塊餐巾(i=l，2，…，N)。餐廳可以從三種途徑(1)新的餐巾，每塊需p分RiN天總的費用最小。pm，快洗所需費用fns。n+11n1天開始每天需要的總 32 33120

0002對所要的餐巾數(shù)進行窮舉開始時其值為所需用餐巾數(shù)之和當(dāng)量太少而周轉(zhuǎn) 的最小費用方案中的最優(yōu)解即為問題的解。程序(見本書光盤)need存放每天需用的fromslowfromfast記錄每天來自快洗的餐巾數(shù)。這個算法的數(shù)量級為O(n)，其中n為所有天中需用的餐巾數(shù)之總和。 接力marathon.???（pas,c,51km、2km、…、10km的所用時間?，F(xiàn)在他要進行一個合理的安2km3km速度快……也就是說連續(xù)跑的路程越長，速度越慢，當(dāng)然也有特殊51510個整數(shù)，表示某一個運動員盡1km、2km、…、10km所用的時間。 3337001200171022402613324539564778 300610960137018002712383448345998 6554298612990156021092896379047475996289577890138119762734387656786890312633995146718452634363648125999給每一個人分配。剩下的里程由哪個選手來跑呢?這時檢查各自所跑第二公里所用的l，下面要檢查的時間段就是他的下一25公里分配完為止。554公里所用的時間。先分配每個運動員跑；剩下的20公里始終選擇所有運動員當(dāng)中下跑的時線性問storage.???（pas,c,磁帶等介質(zhì)信息時基本上都是一種線性的方式，線性方式雖然簡單， 如果有n段信息資料要線性在某種介質(zhì)上，它們的長度分別是L1，L2，…，F(xiàn)1F2…， 41351020303512+Fn=1，如果總的檢索次數(shù)為m，第I段信息資料使用的次數(shù)為m*Fi，設(shè)平均檢索速度為v在第I個信息段前面的所有信息所要的時間，信息段I所有次數(shù)總的時間時：因為上表達式中m、v可看作是常數(shù)，所以單一時間Fi與Li及前面的安排有關(guān)，fan.???（pas,c,個自然數(shù)(0的整數(shù))。扇區(qū)中各選一個數(shù)，相加后形成一個新的數(shù)，請使用這些整數(shù)形成續(xù)的整