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