CodeForces - 51C 修信号站_思维+二分答案
给你x轴上的n个点,可以用三段相同长度的区间进行覆盖,问你这三个区间的最小长度是多少,并输出三段区间的中点。
解题思路:前半个问题应该不难,直接二分答案即可,后半个问题则有些思维成分。另外,这题让我明白了,有时候可以用’精度’换’精度’,由于double的精度问题,有时候求得的值很可能不是与实际值一模一样的。例如,假设二分后的答案是0.500000,这是保留六位小数的效果,但是,它的实际值可能是0.500000999,这样的话,后续可能出错。所以我们在题目精度误差允许的条件下,将它的值-0.0000001。
效果:
后半部分,用二分出来的答案进行贪心覆盖,然后最后看有没有输出三段,如果不足,剩下的都覆盖在最后一个点上即可。special judge,只需满足题意即可。
1 |
|