Parsley_ @ 2024-02-05 21:24:38
为什么越小的最大花费一定越能到达终点？
就是说这个二分单调性是如何证明的？
有一篇题解说：
“回到本题，我们猜测可以使用二分答案后，再验证：由于“我们假设需要的钱”越多，能走的点也就越多，可以走到终点的可能性也就越大，所以，这题是完全可以通过二分答案来写的。”
并不是很能理解，有哪位高人可以帮忙解答吗？能举例，或者严格证明吗？谢谢。
by No_Rest @ 2024-02-05 21:37:12
就是假设答案是 ans，那么比 ans 大的一定能到达终点，因为所以最多交费 ans 能到的点最多交费比 ans 大的都可以到达（根据答案的定义，比 ans 小的也一定不能到达终点），所以满足单调性（好像没说清楚（）