1 条题解
-
0
何老师 (root) LV 0 MOD @ 2024-10-06 11:16:06
二分距离mid(答案区间为1..10^18),然后按贪心指定每个精灵的位置,计算出在社交距离不小于mid的情况下,最多可以放置多少个精灵t,如果t<N,则mid太大,下次mid应该减小,否则可以继续往大猜!
贪心计算最多可以放置的精灵数:把所有食物区间按左端点由小到大排序,指定第一个区间的左端点放置一个精灵,且记下位置p和当前区间i,对于p+mid<=A[i].b,则在第i个区间继续放置一个精灵,否则,考察下一个区间i++,如果p+mid<=A[i].a,则在新区间的开头放置一个精灵,然后继续……,知道把M个区间考察完毕!
- 1