请求修正翻译 & hack & 正解讨论
查看原帖
请求修正翻译 & hack & 正解讨论
128754
方123456楼主2022/9/6 21:03

RT,本讨论帖涵盖了关于本题的几个问题。

首先是翻译的

这个问题造成了做题时的不便,望管理修正。

接着是 hack

在该 hack 下,没有一篇题解活过来,全都被叉。

hack 原因是只取了中位数,没有考虑到原来的点覆盖之后,中位数的最小值可能会发生改变。

另外,本题数据过弱,nn 为奇数的点只有一个,同时数据也很小,nn 为偶数的可以直接用中位数贪,减去不合法的。

当然,以上是关于本题的一些问题,也欢迎有 dalao 来发表自己认为正确的做法。

在这里,我来说明一下我的想法,是对中位数这些点进行摆动,摆动到一个空白的就有可能是答案,就停止摆动,把重复的旁边的空白都拿出来之后,就可以统计答案。

然而这样复杂度似乎有些不太对?但仔细分析一下,复杂度应该是和 nn 点数有关,空白的点也不会超过 nn,同时统计答案的时候利用前缀和+二分优化统计即可。

不清楚上面这种做法是否正确,还请 dalao 指出问题。

2022/9/6 21:03
加载中...