二分-最小值最大化问题
大家好，鄙人第一次写CSDN博客，多多关照，大家共同进步！
什么是最小值最大化问题问题呢？我们以一道经典例题为例：
例题
链接
http://poj.org/problem?id=2456
题目描述（原文）
Description
Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,…,xN (0 <= xi <= 1,000,000,000).
His C (2 <= C <= N) cows don’t like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?
Input
-
Line 1: Two space-separated integers: N and C
-
Lines 2…N+1: Line i+1 contains an integer stall location, xi
Output
- Line 1: One integer: the largest minimum distance
题目大意
沿直线分布的N间房，住C头牛，安排牛的住房，使最近两头牛的距离最大
思考
概念
如果你是第一次看到这样类型的问题，估计也像我一样，没什么头绪。（如果一看就会的我还是orz吧）
当然这道题，我们已经提前收到了一个提示：二分。
但二分和这道题…有啥关系啊？
有！ 数学中，二分法的一个基本应用就是函数思想，逼近最值 。
什么意思？这样的语句依旧晦涩难懂。
自己手画一个二次函数图像试试看。给定查找范围
x
∈
[
l
,
r
]
x\in[l,r]
x∈[l,r]，通过不断的二分，
y
y
y会不断接近最值。
最小值最大化问题，也就是求“最小值”的“最大值”。
所以，按照上面的二次函数的例子，自变量
x
x
x，就是“最小值”，而
y
y
y，就是要求“最小值”的“最大值”。
带入题目情境
在题目中，自变量
x
x
x，就是“最小距离”（minimum distance），而
y
y
y，就是要求“最小距离”的“最大值”（largest minimum distance）。
按照上面的套路，首先，确定
x
x
x的可能范围。
假设我安排N头牛中的两头牛住同一间房，那这C头牛之间的最小距离肯定是0（你总不能整个
−
18
c
m
-18cm
−18cm出来吧
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
