题目连接：HDU3400，leetcode服务中心的最佳位置
这两道题都是三分查找的应用，而且都是三分套三分，通过这两道题让我对三分有了一个初步的了解
这里不对三分法进行说明，如果没有了解过可以看这个:传送门
做完这两道题，我觉得三分本身并不是特别复杂，其实好玩的是证明题目能用三分的过程。
对HDU3400这道题来说，我只能想个大概，证明不出来，引用其他博客的证明：设E在AB上，F在CD上。
令人在线段AB上花的时间为：f = AE / p，人走完Z和Y所花的时间为：g = EF / r + FD / q。
f函数是一个单调递增的函数，而g很明显是一个先递减后递增的函数。两个函数叠加，所得的函数应该也是一个先递减后递增的函数。故可用三分法解之。虽然我看不出这个是先递减后递增的函数，但是可以想个大概。
对于leetcode服务中心的最佳位置来说，题解区证明的非常好，可以看这个：https://leetcode-cn.com/problems/best-position-for-a-service-centre/solution/shu-xue-zheng-ming-by-acw_wangdh15/
这两个题的证明方法，特别是第二道题目的证明方法，让我再一次感受到数学与算法的关系（其实是让我重新过了一遍为什么凸函数加凸函数还是凸函数，为什么凸函数加单调函数还是凸函数 2333），就感觉挺美妙的吧
PS:可以先做leetcode的，再去做HDU(难度是增加的)；leetcode的这道题遍历positions数组的时候用auto的话别忘加&，好多在比赛中做出来的人的亲身体会：会超时
原文：https://www.cnblogs.com/Beic233/p/13296797.html