firehose.cpp

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
int H, k;

vector<int> houses;

bool possible(int w)
{
    for(int i = 0; i < H; i++)
    {
        int left = k - 1;
        int start = houses[i];
        int end = houses[i] + w * 2;

        for(int h = (i + 1) % H; h != i; h = (h + 1) % H)
        {
            //printf("%d\n", pos);
            if(start <= houses[h] && houses[h] <= end || ((end > 1000000) && houses[h] <= (end % 1000000)))
            {
                continue;
            }
            else
            {
                // printf("%d %d %d %d\n", i, end , w, houses[h]);
                left--;
                // printf("%d\n", left);
                start = houses[h];
                end = houses[h] + w * 2;
            }
        }
        if(left >= 0)
        {
            return true;
        }
    }
    return false;
}

int main()
{
    scanf("%d", &H);
    houses.resize(H);
    for(int i = 0; i < H; i++)
    {
        scanf("%d", &houses[i]);
    }
    sort(houses.begin(), houses.end());
    scanf("%d", &k);
    int low = 0;
    int high = 500000;
    while(low < high)
    {
        int center = (low + high) / 2;
        if(possible(center))
        {
            high = center;
        }
        else
        {
            low = center + 1;
        }
    }
    printf("%d\n", high);
}