【捞】求助CSP-S 2020 阅读程序t2

回复帖子

@wandering_trader  2021-09-14 22:42 回复 举报

遇事不决请先问度娘,b站。

连知乎都很难接受这种问题 你觉得洛谷会接受么

@jingkongwanglimiaoa  2021-09-14 23:13 回复 举报

@gaoxinyun0120 @wandering_trader

我已经 bd 过了,可惜学校机房没得截图浏览记录

说这话前建议先自己 bd 一下,看能 bd 出来一个什么破玩意,第一项给我推出来的是 2012 CSP-s 的时空穿越题解,其它的更像一些随记,大概只有作者本人看得懂

之前好像有个嘲讽 bdfs 链接,我觉得它很不错,帮查对应内容。如果真能查到,可以嘲讽对方,如果不能查到,哈哈哈,哈哈,哈就别发了

B站是真的没有想到虽然我觉得在学校机房上B站不太好

关于知乎,我不理解什么叫 连知乎都很难接受把知乎当什么了

发挺长的回复,心平气和无意d人毕竟哪里不好就成我被d,来洛谷就是碰碰运气,看不惯请跳过

另外,如果你通过任何途径找到了能看(懂)的题解,欢迎拿它来打我脸,我不介意

以上 看到一位比一位更强的嘲讽语气,告诉自己保持心平气和

@еcho 2021-09-15 08:55 回复 举报

首先题目求的是区间第 $k$ 小值,常识可知时间复杂度是 $O(n)$ 的。

  1. 不会

  2. 因为是单调递减,第一次会将序列变成单调递增,之后就不会交换了,所以应该是 $O(n)$。

  3. 首先最坏时间复杂度肯定是每次都 rand 到 $L$ 或者 $R$,时间复杂度显然 $O(n^2)$,故排除 B 和 D。又因为输入单调递增,所以平均复杂度为 $O(n)$。

  4. 因为 $d_i$ 为同一个数,显然

while (a < b && d[b] >= d[L])
            --b;

每次都要将整个序列扫一遍,所以是 $O(n^2)$。

@jingkongwanglimiaoa  2021-09-17 00:09 回复 举报

@еcho 谢谢您,这个我看过,但大概算写的比较完整的随记?

我猜也是第 k 小的值(线索:k, 近似排序的代码,题目中的递减),但我比较想知道是怎么个程序逻辑实现的,因为这个程序逻辑不明白,导致我不理解复杂度怎么算,就是这样

谢谢您的解析!

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。