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

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

代碼如下：

#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();
    }
}