先对坐标去重排序。若 cameras≤1 或去重点数不够,没有相邻对或装不下,答案为 0。
最小间距 d 越大越难放满:对 d 二分,再用贪心判定——从最左点起,每次选「与上一台间距 ≥d」的最左可行点,看能否放满 cameras 台。
不能用 (最右−最左)/(cameras−1),因为摄像头只能落在给定挂载点上。样例 [1,2,8,12,13] 装 3 台,均分得到 6,但挂载点上放不下,最优最小间距是 5。
C 语言签名是 maxMinGap(sites, n, cameras),n 为数组长度;返回值为整数,不要把数组内存当字符串打印。
机房走廊上有若干可选挂载点 sites(坐标,未必有序)。要在其中选出恰好 cameras 个位置安装摄像头,每个挂载点最多装一个。
目标:使选出位置按坐标排序后,相邻两台摄像头的间距的最小值尽量大。
选择规则:
cameras 台,且只能放在 sites 给出的坐标上cameras=1,没有相邻对,返回 0cameras,无法每点只装一台,返回 0请返回最优方案下的「最小相邻间距」。
请实现:
maxMinGap(sites: int[], cameras: int) -> int
两行:
sites,形如 [1, 8, 2, 12, 13]cameras约束:
一个整数:最大的「最小相邻间距」。
输入:
[1, 2, 8, 12, 13]
3
输出:
5
说明:去重排序后为 1,2,8,12,13。选 1,8,13,相邻间距 7 与 5,最小为 5。若用 (最右−最左)/(cameras−1) 会得到 6,但挂载点上放不下间距全 ≥6 的三台。
输入:
[5, 5, 5]
3
输出:
0
说明:去重后只剩一个挂载点,装不下 3 台。
输入:
[9]
1
输出:
0
说明:只装一台,没有相邻间距。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册