p1185智力大沖浪

1、貪心法第2題智力大沖浪題目解析：因為不同的小游戲不能準時完成時具有不同的扣款權數(shù)，而且是最優(yōu)解問題，所以本題很容易就想到了貪心法。貪心的主要思想是要讓扣款數(shù)值大的盡量準時完成。方案1：即先把所有的數(shù)據(jù)按照結束時間的先后排序，然后從前向后掃描。當掃描到第n個時段，發(fā)現(xiàn)里面所分配的任務的結束時間等于n1，那么就說明在前面這些任務中必須舍棄一個，于是再掃描第1～n這n個時段，挑出一個最小的去掉并累加扣款值，然后再去調整排列順序，讓后面的元素填

2、補前面的空缺。為了使得取得最大價值，在此將所有的游戲按其規(guī)定期限進行從小到大排序。希望能夠完成足夠多的小游戲。如果當前游戲無法安排下的話，接下來考慮交換論證法。當前游戲的完成期限肯定比之前所有游戲的任何一個已安排的期限要長，因此可以取代前面安排的任何一個游戲。接下來考察其價值。（1）比前面已安排游戲中最小的價值還要小，則該游戲就不用取代前面游戲，直接扣其款數(shù)。（2）比前面已安排游戲中最小的價值要大，則取代前面已安排的游戲中最小價值的那個

3、，并將最小價值的游戲不做，扣其款數(shù)。以上使用的貪心方案在操作過程中，任何一個時間片段內(nèi)，均能取得最優(yōu)方案，能做到步步優(yōu)先，因而該算法就最優(yōu)的！programriddletypedata=recdtimval:longintendarr=array[1..500]ofdatavara:arrijktmnmin:longintprocedureqst(vara:arrlr:longint)varijm:longintt:databegini

4、:=lj:=rm:=a[(ij)div2].tim此處m一定為具體元素值，不可僅保存其下標，因為其下標指向的值可能發(fā)生變化repeatwhilea[i].timnassign(inputriddle.out)reset(output)writeln(m)close(output)end.方案2：因為不能完成的任務，在任意一個時間段中罰款數(shù)目是不一樣的，我們就先把這些任務按照扣款的數(shù)目進行排序，把大的排在前面，先進行放置。假如罰款最多的一

5、個任務的完成期限是k，我們應該把它安排在哪個時段完成呢應該放在第k個時段，因為放在1～k任意一個位置，效果都是一樣的。一旦出現(xiàn)一個不可能在規(guī)定時限前完成的任務，則把其扔到最大的一個空時間段，這樣必然是最優(yōu)的。為了盡可能多地取得更多的價值，很自然地我們盡量考慮讓價值高的游戲先執(zhí)行掉，因而事先先按價值由高到低進行排序。每一個游戲在安排時由于都有一個最低規(guī)定期限，如果該任務可以執(zhí)行的話，很顯然該任務就應該執(zhí)行掉，因為其后面不可能有比它價值更高

6、的游戲了（已排序）。在該游戲所規(guī)定的期限內(nèi)，為了讓后面的游戲在選擇空間上更大，我們只需要選擇該游戲能夠執(zhí)行掉的最遲期限，讓更多的時間選擇片段交給后面游戲提供選擇空間。programriddletypedata=recdtimval:longintendarr=array[1..500]ofdatavara:arrhash:array[1..500]ofboolean游戲是否可以選擇，布爾類型數(shù)組更方便ijmnmin:longintfla