2016 Silver January p1

题目

给出 N 个草垛的坐标以及能用的奶牛数量 K,要求得出只用 K 只奶牛能炸完所有草垛的奶牛最小爆炸半径。

思路

由于爆炸半径大于等于最小爆炸半径就一定能炸完所有草垛,小于就一定炸不完,所以可以用二分查找法来找到最小半径。

复杂度分析

在 n 个元素中用二分查找法找到某个元素的复杂度为O(logn),每次选择一个元素后检查是否合法的复杂度为 O(n),因此整个二分法的复杂度为O(n logn)。K 的范围是 1 - 10,草垛数量的范围是1 - 50000,时间复杂度最大约为 10 log50000,因此不会超时