Preparing NOJ

区间覆盖问题

1000ms 65536K

Description:

x1 , x2 ,… ,xn是实直线上的n个点。用固定长度的闭区间覆盖这n个点,至少需要多少个这样的固定长度闭区间?设计解此问题的有效算法,并证明算法的正确性。

对于给定的实直线上的n个点和闭区间的长度k,编程计算覆盖点集的最少区间数。

Input:

第一行有2 个正整数nk,表示有n个点,且固定长度闭区间的长度为k。接下来的1 行中,有n个整数,表示n个点在实直线上的坐标(可能相同)。

Output:

将编程计算出的最少区间数输出。

Sample Input:

7 3
1 2 3 4 5 -2 6

Sample Output:

3

Note:

undefined

本题由旧版NOJ导入,来源:NUAA

Info

NOJ

Provider NOJ

Code NOJ1258

Tags

Submitted 3

Passed 1

AC Rate 33.33%

Date 04/20/2019 10:03:10

Related

Nothing Yet