zcmimi's blog

arrow_back贪心共25篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先把所有(替换成),然后每次遇到(cnt++,否则cnt--,如果cnt<0,那么从前面的问号中挑一个从)改成(费用最小的替换掉

如果最后没法使cnt=0,那么就输出-1

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先按左端点排序,每次添加右端点的时候如果堆中个数等于k就统计答案,然后弹出最小的右端点

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

把工作按截止时间排序,如果当前时间没到截止时间,那么答案加上它的价值,然后往小根堆中插入它的价值

否则,如果他的价值比堆顶大,那么答案加上它的价值减去堆顶,删除堆顶,插入它的价值

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

算法:贪心+堆维护

贪心策略:

我们考虑先按t贪心,中途再更改。 按t从小到大排序之后,开始轮流遍历每个建筑。 如果中途某个建筑i无法在t_it的时间内修复,那么在先前选择修复的建筑中拿出a_j最大的j号建筑。若a_i < a_j,则放弃j转而修i

策略证明:

若第i号出现时间不足,那么前i个建筑中最多修复i-1个建筑 则我们必然选择a_i较小的前i-1个建筑,给后面的修复留下更多的时间 实现方法:

使用堆来维护选择的建筑中a_i最大的。

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

解法1:

贪心

把深度大于2的都加到堆中

每次取出深度最大的点

从根结点往它父亲连边

然后把周围的节点标记为已经覆盖

解法2:

树形dp

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

我们可以发现交换相邻两个位置用2操作更优,其他的用1操作

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

2/3
Search
search