<span>【题解】P7806 「DCOI2021」A 冰魄吐息</span>
首先二分 \(d\),对每一个点 \(i\),考虑找到一个区间 \([L_i,R_i]\) 满足:
当且仅当 \(k\in[L_i,R_i]\),直线 \(y=kx\) 能够覆盖点 \(i\)。
原问题转化为一个经典问题:\(N\) 条线段,最少点数覆盖它们。
考虑直接贪心解决,按照结束时间从小到大排序,每次选择一个区间的右端点即可。
Author 的 std 复杂度是 \(O(\log\times N\times\log)\),第一个是二分的 \(\log\),第二个是求斜率区间的 \(\log\)。