p1185智力大沖浪

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

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

3、，并將最小價(jià)值的游戲不做，扣其款數(shù)。以上使用的貪心方案在操作過程中，任何一個(gè)時(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一定為具體元素值，不可僅保存其下標(biāo)，因?yàn)槠湎聵?biāo)指向的值可能發(fā)生變化repeatwhilea[i].timnassign(inputriddle.out)reset(output)writeln(m)close(output)end.方案2：因?yàn)椴荒芡瓿傻娜蝿?wù)，在任意一個(gè)時(shí)間段中罰款數(shù)目是不一樣的，我們就先把這些任務(wù)按照扣款的數(shù)目進(jìn)行排序，把大的排在前面，先進(jìn)行放置。假如罰款最多的一

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

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