LG 4053 [JSOI2007]建筑抢修

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转算法:贪心+堆维护贪心策略:我们考虑先按$t$贪心,中途再更改。按$t$从小到大排序之后,开始轮流遍历每个建筑。如果中途某个建筑$i$无法在$t_it$的时间内修复,那么在先前选择修复的建筑中拿出$a_j$最大的$j$号建筑。若$a_i < a_j$,则放弃$j$转而修$i$策略证明:若第$i$号出现时间不足,那么前$i$个建筑中最多修复$i-1$个建筑则我们必然选择$a_i$较小的前$i-1$个建筑,给后面的修复留下更多的时间实现方法:使用堆来维护选择的建筑中$a_i$最大的。……