一个最大一维覆盖问题
在一个一维轴上
有一系列点 x1 x2 x3 x4.... xn
每个点的坐标已知
问对于给定的长度length
最大可以覆盖多少个点 打印出来所有的点
[解决办法]
可以以n/2作为分界点。
递归求左边的分界点数,右边的分界点数。
最后和包含的分界点数,求最大值。
[解决办法]
1. 对n个点排序, 从小到大 v1, v2, ..., vn
2. num = 0; pos = 0
3. for (i = 1; i <=n; i++)
用二分查找找到(vi=length)能插入的位置j, 令num(i)=j-i
如果num(i) > num, num = num(i), pos = i
4. 打印v(pos)到v(pos+num-1)