【APIO2016】Gap


子任务1分析

这个比较简单

我们首先通过询问最大值和最小值得到这个序列的第一项和最后一项

然后依次缩小范围,可以整个序列,这样的询问次数恰好符合标准

然后我们只要用\(O(n)\)来得到相邻差的最大值即可

子任务2分析

我们首先必须询问\([0,10^{18}]\),得到最小值\(x\),最大值\(y\),这次询问的代价为\(n+1\)

然后就需要用到一个数学技巧

设\(L=[\frac {(s1-t1)}{N}]\)(向上取整),显然最终的答案一定会大于等于平均值\(L\)

所以当我们只用关心区间内的最小值和最大值即可

这样我们一次询问长度为L的区间,理论上代价和为\(3n-1\),正好AC

不知道为什么,我的询问次数都是\(3n\),~~可能是我比较菜~~不过也能过QAQ

下面给出完整的代码

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 16,379

Categories

Archive

Comments