ZIO 2013:玩偶

Question

你的商店出售几种不同类型的娃娃。每个娃娃都有一个建议价格，没有两种玩偶有相同的价格。您希望为每个娃娃确定一个实际的销售价格，以便不同类型的娃娃在价格上尽可能不同。由于政府的一些规定，你只能在±K的固定区间内修改建议价格，换句话说，如果建议的价格是p，你可以选择{p−K，p−K+ 1范围内的任何销售价格。。。，p+ K−1，p+ K}.当然，销售价格必须始终是非负的.例如，假设有四种玩偶，建议价格为130、210、70和90，允许你在20的范围内修改价格，然后，你可以分别将价格调整到150、210、50和100，使任意两种玩偶之间的最低差价为50。(对于第二个娃娃，你可以选择200到230之间的任何价格。)在给定约束条件下，您可以检查这是可以实现的最大分离。

在以下每一种情况下，您都会得到一个价格序列和K的值，如果允许您将每个价格修改为向上的±K，则必须确定序列中所有对之间的最大分离。

(a) K= 13.序列: 144、152、214、72、256、3、39、117、238、280。 (b) K= 10.序列: 10、48、57、32、61、74、33、45、99、81、19、24、101。 (c) K= 20.序列: 10、19、154、67、83、39、54、110、124、99、139、170

所以基本上，我只需要在没有编码的情况下找到最大分离的值。我试图设计一种算法，但不幸地失败了，所以我刚开始用蛮力强迫它，基本上将每个价格增加/降低一个值，但是这里使用的强制强制太难了，因为K的值(对于任何K<6来说都会很简单)。

有人能定义一个函数或递归关系来计算它吗？解决方案在线，但它们只给出一个整数的答案，不解释如何到达解决方案。我是一个编程初学者，所以请试着用伪代码/一点点C++来解释。谢谢。

资料来源：http://www.iarcs.org.in/inoi/2013/zio2013/zio2013-qpaper.pdf解决方案：http://www.iarcs.org.in/inoi/2013/zio2013/zio2013-solutions.pdf

Answer 1

这是一个O(nlogn)算法。

为了说明我将使用第二个例子: 10，48，57，32，61，74，33，45，99，81，19，24,101与K=10

1. 对清单进行排序(10、19、24、32、33、45、48、57、61、74、81、99、101)
2. 用二分法求最小分离x

对于x的试用值，将最后的值贪婪地放置在尽可能小的位置，同时满足条件(非负的，在原始值的K内，至少比以前的x大)。

因此，让我们从x=10开始，我们将采取如下步骤：

1. 10->0 (不能变成负值，所以这是最小允许的)
2. 19->10 (不能在前一个值的K=10内)
3. 24->20
4. 32->30
5. 33->40
6. 45->50
7. 48变成不可能。我们只能分配38到58之间的值，但这些值中没有一个比之前的50个多出10个。

我们的结论是，x=10太高，分离，我们需要移动较低。您可以尝试x=7并发现这是可能的，x=9发现这是不可能的，然后尝试x=8：

1. 10->0
2. 19->9 (只能移动到9->29)
3. 24->17
4. 32->25
5. 33->33
6. 45->41
7. 48->49
8. 57->56
9. 61->64
10. 74->72
11. 81->80
12. 99->89
13. 101->97

因此我们发现x=8是可能的，x=9是不可能的，因此x=8是最大可能的分离。