[LC周赛赛后发布会]WeeklyContest359

来来来，手速场手速场，我们今天早点开，开完早点睡觉。


第三题是国人都喜欢的买房哈哈，真的是买房，土豪买房。LZ变量名都是offer offer，非常吉利。


虽然是手速场，但是LZ这里还是出了个插曲：
第三题LZ TLE了好几次。我们假设位置空间是M，然后offer的空间是N，根据题意，这两个应该都是10_000。然后LZ用了个list（java，就是数列）去存储所有的offer，也就是一个M的array，存N个offer，然后就是用offer的end作为index（当前位置没offer就是空的咯）。这个复杂度应该是M + N，也就是O（10_000)，因为M和N是一个量级的。但是超时！LZ一开始还以为是系统忙超时，因为诡异的是它下面没有之前的“hidden test case”，LZ retry了好几次（因为对复杂度有信心）。LZ想了一下感觉还是优化成map吧，也就是Map<End -> list of offers with this end>，然后就过了。
其实复杂度本来就是O(M + N)，因为你后面要iterate 位置空间O（N）的。LZ因为这个多了几个TLE，在手速场里可以说是致命的。


第四题没秒，还是想了一会的。
搞下来还不如上周速度3题呢......搞到最后才5%......都是那几个同复杂度TLE害得。不过话说回来，就算把罚时拿掉，LZ估计也就3%开外，也没差多少。


另外上周就emo了，emo到现在，有机会单开个帖子。

最后一题好像可以二分，我是按照数字分类然后逐个用deque计算的

mrn3088 发表于 2023-8-20 02:20
最后一题好像可以二分，我是按照数字分类然后逐个用deque计算的

二分反而慢，deque快，有点像双指针