小H去美国假期实践的时候遇到了一件很有趣的事情。
话说小H的导师家的别墅后,有一块很大的草坪。本来这是一件很和美的事情。但是,草坪的后面就是一块小森林,森林里面的兔子总是跑到草坪上来吃草。当然了,吃些草倒是没什么,但是兔子们总是将他们的排泄物留在草坪上,使得主人家的两只牧羊犬吃了它们的排泄物之后总是拉肚子。于是,小H的导师需要建一道篱笆,将后院的草坪围起来。
篱笆销售商已经将一些标准大小的篱笆放置在草坪的边界上了。这些篱笆的长度足够覆盖整个草坪的边界,但是现在的摆放却留下了很多的空隙。然而篱笆既重又难以放置,每次放下都会毁坏一些草。因此,小H及其同伴希望找出一组篱笆的放置方法,使得所有篱笆中移动最远的一段,移动的距离最少。
抽象来说,草坪的边界可以看做一个[0,L]的区间,既有可能是一条直线,又有可能是环形的。每块篱笆的中点为C_i,可以覆盖[C_i-r,C_i+r]的范围(环形的情况类似)。我们希望移动后的篱笆覆盖的区间包含整个边界。
由于篱笆销售商提供的篱笆数量比较多,小H及其同伴希望知道,对于询问(X,Y),如果只是用编号为X到Y的篱笆,这个最短的移动距离是多少。这样他们就可以将多余的篱笆退回,毕竟浪费可耻嘛~~。
话说小H的导师家的别墅后,有一块很大的草坪。本来这是一件很和美的事情。但是,草坪的后面就是一块小森林,森林里面的兔子总是跑到草坪上来吃草。当然了,吃些草倒是没什么,但是兔子们总是将他们的排泄物留在草坪上,使得主人家的两只牧羊犬吃了它们的排泄物之后总是拉肚子。于是,小H的导师需要建一道篱笆,将后院的草坪围起来。
篱笆销售商已经将一些标准大小的篱笆放置在草坪的边界上了。这些篱笆的长度足够覆盖整个草坪的边界,但是现在的摆放却留下了很多的空隙。然而篱笆既重又难以放置,每次放下都会毁坏一些草。因此,小H及其同伴希望找出一组篱笆的放置方法,使得所有篱笆中移动最远的一段,移动的距离最少。
抽象来说,草坪的边界可以看做一个[0,L]的区间,既有可能是一条直线,又有可能是环形的。每块篱笆的中点为C_i,可以覆盖[C_i-r,C_i+r]的范围(环形的情况类似)。我们希望移动后的篱笆覆盖的区间包含整个边界。
由于篱笆销售商提供的篱笆数量比较多,小H及其同伴希望知道,对于询问(X,Y),如果只是用编号为X到Y的篱笆,这个最短的移动距离是多少。这样他们就可以将多余的篱笆退回,毕竟浪费可耻嘛~~。