package main

import "sort"

func maxDistance(position []int, m int) int {
	sort.Ints(position)
	left := 1
	right := position[len(position)-1] - position[0]
	ans := -1
	for left <= right {
		mid := left + (right-left)/2
		if check(mid, position, m) { // 两两之间距离为mid的时候能放下m个球，那么说明距离还可以大一些
			ans = mid
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return ans
}

// 距离为mid的时候，能否放下m个球
func check(mid int, position []int, m int) bool {
	prePos := position[0]
	cnt := 1
	for i := 0; i < len(position); i++ {
		if position[i]-prePos >= mid {
			prePos = position[i]
			cnt++
		}
	}
	return cnt >= m
}

// 二分法
// 最大化的最小磁力 最小磁力 其实就是两球之间的距离
// 男生上厕所问题
// n个小便池，站m个男生
// 设两两之间的距离是mid，判断能否站下m个人