首页 > 其他 > 详细

一句话题解(2020.4.10 ~)

时间:2020-04-10 23:54:28      阅读:110      评论:0      收藏:0      [点我收藏+]

  日常偷懒

  有些题因为实在太懒了,所以没写,如果在口胡还望各路大佬能指正。

UOJ

  • 386,考虑按大小排序,然后枚举最大的大小,考虑从大到小枚举较小值,显然你会贪心地选其中牢固程度最大的 $m$ 个。然后考虑用链表维护能够加入后缀 $m$ 大的所有数,显然除了最初的 $m$ 个一定是单调递增的。每次暴力从后往前遍历链表,将里面的数加入某个数据结构,如果不能加入就把这个数从链表上删除,如果这个数以及比新加入的大,那么就停止遍历。每次只用枚举到的地方更新答案。对于不在最初 $m$ 个数最多被遍历 $m$ 次,通过一些简单的 trick 可以做到 $O(nm)$。

 

一句话题解(2020.4.10 ~)

原文:https://www.cnblogs.com/yyf0309/p/12676784.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!