RT,本讨论帖涵盖了关于本题的几个问题。
首先是翻译的
这个问题造成了做题时的不便,望管理修正。
接着是 hack
在该 hack 下,没有一篇题解活过来,全都被叉。
hack 原因是只取了中位数,没有考虑到原来的点覆盖之后,中位数的最小值可能会发生改变。
另外,本题数据过弱,n 为奇数的点只有一个,同时数据也很小,n 为偶数的可以直接用中位数贪,减去不合法的。
当然,以上是关于本题的一些问题,也欢迎有 dalao 来发表自己认为正确的做法。
在这里,我来说明一下我的想法,是对中位数这些点进行摆动,摆动到一个空白的就有可能是答案,就停止摆动,把重复的旁边的空白都拿出来之后,就可以统计答案。
然而这样复杂度似乎有些不太对?但仔细分析一下,复杂度应该是和 n 点数有关,空白的点也不会超过 n,同时统计答案的时候利用前缀和+二分优化统计即可。
不清楚上面这种做法是否正确,还请 dalao 指出问题。