rt,我一开始看到这个题大多数题解都没有为了特判 wqs 二分中一个斜率可能会切到很多点的情况,而强制选择 权值最小的方案中选择段数最多的那种,是这个题没有特意去卡吗?
其次,这个题所有人的 wqs 二分斜率取值范围也不相同,例如 Drind 的题解中设成了 0 到正无穷,按理来说对下凸壳做 wqs 二分不应该下限为正无穷吗?但我按照此想法进行测试了一组大样例后得出了一个很奇怪的答案。
而我尝试把该程序下限设成 0 并测试上述样例,并输出最优解斜率取值和取到的段数,此时程序找出的最优解斜率取值为 0,但是此时返回的选择段数远低于要求段数,但是还是得出了正确答案,这是因为我在第一段中说到的特殊情况还是什么神秘原因,总之不是很懂。