二分+贪心 boj1393 WiFi

WiFiSubmit: 32   Accepted:14Time Limit: 1000MS  Memory Limit: 65536KDescription
One day, the residents of Main Street got together and decided that they would install wireless internet on their street, with coverage for every house. Now they need your help to decide where they should place the wireless access points. They would like to have as strong a signal as possible in every house, but they have only a limited budget for purchasing access points. They would like to place the available access points so that the maximum distance between any house and the access point closest to it is as small as possible.
Main Street is a perfectly straight road. The street number of each house is the number of metres from the end of the street to the house. For example, the house at address 123 Main Street is exactly 123 metres from the end of the street.


Input
The first line of input contains an integer specifying the number of test cases to follow. The first line of each test case contains two positive integers n, the number of access points that the residents can buy, and m, the number of houses on Main Street. The following m lines contain the house numbers of the houses on Main Street, one house number on each line. There will be no more than 100 000 houses on Main Street, and the house numbers will be no larger than one million.

Output
For each test case, output a line containing one number, the maximum distance between any house and the access point nearest to it. Round the number to the nearest tenth of a metre, and output it with exactly one digit after the decimal point.


Sample Input

1
2 3
1
3
10


Sample Output

1.0

题目描述：
在一条直线上有不定数量的房子，给指定个数的wifi热点，需要用这些wifi热点来覆盖这些房子。下面这句话是关键：
They would like to place the available access points so that the maximum distance between any house and the access point closest to it is as small as possible.
翻译为：我们需要找到这样一个最小值，它是满足所有房子的最大距离(这个最大距离定以为：任何一个房子与距离它最近的一个wifi热点之间的距离)中的最小值。

解题思路： 二分+贪心
二分：
二分的应用条件：答案必须具有单调性，在本题中,单调性体现在：如果存在一个最大距离a，那么一定存在一个最大距离b>a也满足条件。
二分：将房子的坐标排序，找到最大的坐标M，我们需要查找的结果就在0~M之间，二分之，判断每个二分后的值是否满足条件(即能否用指定数量的wifi覆盖到所有房子)。
如果满足条件，缩小二分范围的最大值为当前值，继续。
如果不满足条件，说明当前值选小了(以至于不能覆盖所有房子)，缩小二分范围的最小值为当前值，继续
其实这个二分就是不断二分查找最接近目标值的方法。

贪心：
根据跟定的测试值，从左到右，用一个wifi来覆盖尽可能多的房子，然后从下一个未覆盖的点开始重复执行这个过程，判断wifi数量是否足够。

下面是我的代码：
#include 
#include 
#include 
using namespace std;

#define MIN 0.001

int wifi, nb_res;
double houses[100010];

int cmp(const void *a, const void *b)
{
    double *pa = (double *)a;
    double *pb = (double *)b;
    return *pa - *pb;
}

/*二分查找*/
int find_next(double start, double range)
{
    int mid, front = 0, rear = nb_res - 1;
    double target;
    target = start + range;
    if (target > houses[nb_res - 1])
        return -1;
    while (front <= rear)
    {
        mid = (front + rear) / 2;
        if (target > houses[mid])
            front = mid + 1;
        else
            rear = mid - 1;
    }
    return front;
}

int fit_rule(double distance)
{
    int available = wifi, next;
    double range, start;
    start = houses[0];
    /*覆盖范围是左右两边，所以翻倍*/
    range = distance * (double)2.0;
    /*available表示可用wifi数量*/
    while (available--)
    {
        /*查找未被覆盖的下一个房子，采用二分查找(坐标已排序)*/
        next = find_next(start, range);
        if (-1 == next)
            return 1;
        start = houses[next];
    }
    return 0;
}

double binary_find(double front, double rear)
{
    int ret;
    double mid;
    /*在这个循环中不断缩小查找范围，不断接近目标值*/
    while (fabs(front - rear) > MIN) /*MIN是精度*/
    {
        mid = (front + rear) / (double)2.0;
        ret = fit_rule(mid);
        /*如果mid满足条件，调整rear=mid*/
        if (1 == ret)
            rear = mid;
        /*如果mid不满足条件，调整front=mid*/
        else
            front = mid;
    }
    return front;
}

int main(int argc, char *argv[])
{
    int N, i, front, rear;
    double max, ret;
    cin >> N;
    while (N--)
    {
        cin >> wifi >> nb_res;
        for (i=0 ; i            cin >> houses[i];
        qsort(houses, nb_res, sizeof(double), cmp); /*排序坐标*/

        max = houses[nb_res - 1];
        ret = binary_find(0.0, max); /*二分之，从0~最大坐标*/
        printf("%.1lf\n", ret);
    }
}