每日一题: Best Cow Fences(二分)
题意
给定一个正整数数列A，求一个平均数最大的、长度不小于L的子段。
solution
考虑check问题，正着枚举起点，我们需要知道每个起点所能枚举的最大值。当一个数大于当前二分的平均数时，它一定是对答案有贡献的，因此倒过来预处理每个起点能枚举到的最大值即可。时间复杂度 $O(nlogn)$。
给定一个正整数数列A，求一个平均数最大的、长度不小于L的子段。
考虑check问题，正着枚举起点，我们需要知道每个起点所能枚举的最大值。当一个数大于当前二分的平均数时，它一定是对答案有贡献的，因此倒过来预处理每个起点能枚举到的最大值即可。时间复杂度 $O(nlogn)$。
给定一个长度为 $n$ 的数组 A ，把所有长度 >= $k$ 的区间中的第 $k$ 大值插入 B 数组中，求 B 数组的第 $m$ 大数。
这种显然二分答案题我们主要关心 $check$ 问题。
Update your browser to view this website correctly.&npsb;Update my browser now