题解

1 条题解

  • 0
    @ 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

信息

ID
2193
难度
9
分类
其他 | 二分查找贪心 点击显示
标签
(无)
递交数
1
已通过
1
通过率
100%
被复制
3
上传者