#PU594. USACO 2016 January Contest, Silver — Problem 1. Angry Cows

    ID: 1449 传统题 文件IO:angry 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:jan16来源:usaco.orgscoring:equal_test_cases二分答案

USACO 2016 January Contest, Silver — Problem 1. Angry Cows

USACO 2016 January Contest, Silver — Problem 1. Angry Cows

题目描述

Bessie the cow has designed what she thinks will be the next big hit video game: "Angry Cows". The premise, which she believes is completely original, is that the player shoots cows with a slingshot into a one-dimensional scene consisting of a set of hay bales located at various points on a number line. Each cow lands with sufficient force to detonate the hay bales in close proximity to her landing site. The goal is to use a set of cows to detonate all the hay bales. There are NN hay bales located at distinct integer positions x1,x2,…,xNx_1, x_2, \ldots, x_N on the number line. If a cow is launched with power RR landing at position xx, this will causes a blast of "radius RR", destroying all hay bales within the range x−R…x+Rx-R \ldots x+R. A total of KK cows are available to shoot, each with the same power RR. Please determine the minimum integer value of RR such that it is possible to use the KK cows to detonate every single hay bale in the scene.

输入格式

The first line of input contains NN (1≤N≤50,0001 \leq N \leq 50,000) and KK (1≤K≤101 \leq K \leq 10). The remaining NN lines all contain integers x1…xNx_1 \ldots x_N (each in the range 0…1,000,000,0000 \ldots 1,000,000,000).

输出格式

Please output the minimum power RR with which each cow must be launched in order to detonate all the hay bales.

数据范围

(见题面原文)

样例

样例 1

7 2
20
25
18
8
10
3
1
5
Problem credits: Brian Dean