市賽很糟糕，差點(diǎn)連市隊(duì)都沒(méi)進(jìn)。
1.數(shù)學(xué)題，結(jié)果要用高精輸出。
2.DP，有一個(gè)狀態(tài)忘記轉(zhuǎn)移了。。爆0
3.SPFA。
4.說(shuō)不清是什么算法，所以我們重點(diǎn)來(lái)討論一下第四題。
/*考試的時(shí)候一直在找O（n）的算法。。。。。結(jié)果10分
回家后用了一個(gè)類似于貪心的算法。
遞降time，維護(hù)一個(gè)heap，每次賣出最有價(jià)值的。
在linux下用set寫的AC，pritory__queue寫的超時(shí)2個(gè)點(diǎn)。
結(jié)果在cena下pritory__queue，AC，set：90（TLE）
然后在windows手測(cè)，發(fā)現(xiàn)set反而更快。
發(fā)現(xiàn)cena嚴(yán)重糟搞。
還有最后一個(gè)點(diǎn)錯(cuò)了，。out是超出longint后溢出的結(jié)果。。。*/
其實(shí)仔細(xì)想想這是一個(gè)貪心問(wèn)題，二其考察點(diǎn)在于數(shù)據(jù)的處理。
顯然在一組可行解中，價(jià)值商品比價(jià)值小的好，時(shí)間早的比時(shí)間遲的好。
我的第一種解法，就是枚舉time遞降（考慮最壞情況），
維護(hù)比賣出在當(dāng)前時(shí)刻可以賣出的最大價(jià)值的商品。實(shí)現(xiàn)時(shí)就是一個(gè)堆。
但存在有時(shí)間點(diǎn)上沒(méi)有任何商品能賣出，所以時(shí)間有一定的浪費(fèi)。
T（n）=O（nlogn）。說(shuō)過(guò)了，這時(shí)間復(fù)雜度有一點(diǎn)懸。
后來(lái)聽聞了另一種解法。按價(jià)值從大到小選取商品，將它放在它可以賣出的最后的時(shí)間點(diǎn)上。
當(dāng)然存在這一時(shí)間點(diǎn)上已經(jīng)有物品放置了，
所以我們需要維護(hù)一個(gè)數(shù)組pre[x]表示x時(shí)間前的第一個(gè)空閑時(shí)間。
這里可以想到用并查集，當(dāng)然這不是常規(guī)的并查集，合并時(shí)pre[x]轉(zhuǎn)化成最小的pre[i]。
T(n)=O(nα(n))是足矣的。由于我前面漏了一節(jié)LCA和RMQ的課,Tarjan還不會(huì)寫，想不到很正常。
發(fā)現(xiàn)貪心的題目一直不是很擅長(zhǎng)。
繼續(xù)總結(jié)，
1.找到必勝態(tài)（貪心終止條件，也可以認(rèn)為是其實(shí)條件。有時(shí)沒(méi)有。）
2.發(fā)現(xiàn)單調(diào)性（這一步就是比較不同狀態(tài)的優(yōu)劣性，發(fā)現(xiàn)深層次的問(wèn)題。）
3.研究轉(zhuǎn)化策略（怎樣從一個(gè)狀態(tài)到必勝態(tài)，怎樣轉(zhuǎn)化成一個(gè)更優(yōu)的狀態(tài)）
有時(shí)候要做一些最壞的假設(shè)。