:題目例子：http://acm.zjgsu.edu.cn/JudgeOnline/showproblem?problem_id=1277
題目的大意是：
有N個房子在一條街上，（街是條直線）每個房子有個離這個街的最末端得距離。現(xiàn)在要在這條街上安裝m個路由器 使得每個房子都能有個距離最近的路由器。并且使得所有房子和它距離最近的路由器之間的距離最大一個是最小的。
初一想就是 一個經(jīng)典DP問題..
比如考慮 兩個房子 一個路由器.肯定是將路由器放在中間位置..
于是對房子的距離排個序 就可以很快得出一個DP的表達式。
F[i,k]表示前i個房子放k個路由器的最優(yōu)解..
則F[i,k]=min{max(F[j,k-1],(house[i]-house[j+1])/2),1<=j<i}
表示前j個房子放k-1路由器，第K個路由器放在第j+1和第i個房子的中點..
算法是O(m*n^2) 對于數(shù)據(jù)兩n<=100000 無論如何都優(yōu)化不了的DP 已經(jīng)難以解決這個問題了..
后來經(jīng)同實驗室的朋友介紹了一個算法參數(shù)搜索的應(yīng)用..
并找到一個論文.http://acm.zjgsu.edu.cn/Software/canshusousuo.doc(汪汀 著) 轉(zhuǎn)載至中華信息網(wǎng)

關(guān)于怎么解這個問題就不多說了..就是找最優(yōu)解.首先找一個最小的解，最大解，然后二分判斷這個某個解是否是可行解。

代碼如下：

#include<iostream>
#include<algorithm>
using namespace std;
int house[100002];
int n,m;
bool isok(int value)
{
    int i=1,j,p=1;
    for(j=1;j<=n;j++)
    {
                if(i>m) return false;
        if((house[j]-house[p])*10>value*2)
        {
            p=j;
            i++;
        }
    }
    if(i<=m)
        return true;
    return false;
}
void AC()
{
    int ans;
    int low=0,hight=(house[n]-house[0])*10,mid;
    while(low<=hight)
    {
        mid=(low+hight)/2;
        if(isok(mid))
            hight=mid-1;
        else
            low=mid+1;
    }
    if(isok(low))
        ans=low;
    else
        ans=hight;
    printf("%.1lf\n",ans*1.0/10);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&m,&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&house[i]);
        house[0]=0;
        sort(house,house+n+1);
        AC();
    }
}