代码分析
ppt中 【核心代码】
//由于精度差问题,考虑先将面积 *1000000转化为整数来二分 long long res,mid; while (low <= high)//untilend,not == {//low = 0,high = max(size[i]) mid = (high + low) / 2; if (judge(mid) ) { low = mid + 1; res = mid; //最后结果为res } else { high = mid - 1; } } bool judge(long long mid) { long long p = 0; for (int i = 0; i < n; ++i) { p += size[i] / mid;//相当于面积为自变量、可行人数为函数值了 } return p >= f; }
直接的考虑是:用较大面积除以人数的【重合部分】,但是需要比较人数的重合与最大面积&次大面积的组合,混乱!
用函数值判断!反正除法,除数和商是可以互换的。
n个个体分成m部分类型的问题,不是直接考虑m如何,而是从总和入手。。