第四题《麻烦的第K大问题》的思路

0
0

二分答案ans
把原数组中大于等于ans的看成len-y,小于ans的看成-y
然后统计多少个(长度是len倍数的)区间总和大于等于0,记作C

根据C和K的大小关系决定向左还是向右二分答案

比赛中的数据有点弱,赛后会加一个(len比较小的)数据。大家可以在题库里再试试。

3 answer(s)

0

前两题的思路能麻烦稍微讲一讲吗?谢谢?

0

请问,有没有参考代码

0

统计多少个(长度是len倍数的)区间总和大于等于0, 这个怎么做?

  • 请教了我校学弟大佬,得到了一个big-small做法,根据数据范围,大于500暴力,小于500按前缀偏移%len放到树状数组内统计,勉强通过,不知道还有啥别的套路做法。。。

  • len大于500也可以按前缀偏移%len放到树状数组内统计吧。 不管len大小总共就是N次插入+查询。

  • @96655 大佬能把代码发给我学习一下吗1318531213@qq.com,谢谢!

  • 谢谢管理员

  • 添加评论
  • reply

write answer 切换为英文 切换为中文


转发分享