前段时间做了这道题,有这样一个猜想:
如果一个点x0满足条件那么最大的ti+|xi-x0|和次大的一定相等
想问一下dalao们这个猜想是否正确,如果正确,怎么用这个结论写这道题(可以看一下下边本蒟蒻的做法)
我是把它反过来,也就是
对于一个点xj,如果最大的和次大的ti+|xi-xj|相等,那么xj就是满足条件的x0。
交上去之后发现这个逆猜想不一定成立,比如下边这组数据:
n=5
x: 1 2 3 4 5
t: 100 101 0 0 0
我的程序刚开始是从中间开始找的,这组数据中是从x3开始找
对于点x3,最大值和次大值分别是 t1+|x1-x3|=100+2=102 和 t2+|x2-x3|=101+1=102,相等,此时程序会认为点x3就是x0
但实际上,x0应该在1.5,最大值=次大值=100.5
后来尝试改,但是太改起来麻烦了,本蒟蒻还是去用题解的方法罢