日常偷懒。
有些题因为实在太懒了,所以没写,如果在口胡还望各路大佬能指正。
UOJ
- 386,考虑按大小排序,然后枚举最大的大小,考虑从大到小枚举较小值,显然你会贪心地选其中牢固程度最大的 $m$ 个。然后考虑用链表维护能够加入后缀 $m$ 大的所有数,显然除了最初的 $m$ 个一定是单调递增的。每次暴力从后往前遍历链表,将里面的数加入某个数据结构,如果不能加入就把这个数从链表上删除,如果这个数以及比新加入的大,那么就停止遍历。每次只用枚举到的地方更新答案。对于不在最初 $m$ 个数最多被遍历 $m$ 次,通过一些简单的 trick 可以做到 $O(nm)$。
一句话题解(2020.4.10 ~)
原文:https://www.cnblogs.com/yyf0309/p/12676784.html