使给定数组严格增加所需的最小更改

Question

我正试图解决SPOJ http://www.spoj.com/problems/DOSA这个问题，这也是一个采访的问题。

我的逻辑是从给定的数组中获取满足ai>i (基于0的索引)的元素，因为其他元素总是需要更改。

现在从这些选定的元素中找出最长的严格递增子序列，最后的答案是数组的原始长度--计算的LIS示例:原始数组是:1 7 10 2 20 22

按ai>i计算的新数组为1 7 10 20 22。

现在，这个数组的LIS是5。

所以，最后的答案是6-5=1。

但它给出了错误的答案，任何人都可以指出我的逻辑哪里是错误的。

编辑:问题陈述: Lalith要吃饭，他面前有N个剂量，价格由整数序列a1、a2、a3...an表示。

他决定以不同的方式吃东西。您可以自由地用任何正整数替换任何多萨的价格。

必须替换多少个价格(整数)才能使结果序列严格增加？

样本输入:6

1 7 10 2 20 22

样本输出:1

Answer 1

你的推理可能有点错误。

请考虑以下示例：

10
2 3 4 2 5 6 7 8 9 10

在这里，答案是4(需要更改前4项输入)，但根据原海报的逻辑，如果我们去掉：

A[i] less than or equals i

我们会得到一个剩余的号码列表：

​

2 3 4 5 6 7 8 9 10

如果LIS直接应用于它(整个序列严格增加，并且只丢弃原始数组中的A3 )，它的答案显然是1。

方法

我的做法如下：

1. 试着建造LIS。也就是说，保持数组Ai，使Ai =增加的序列中最低的I-项，到目前为止，发现还遵守以下规律，即它在Ai值的输入数组中的索引与指数Ai-1有差异，因此：

- The difference between their respective values is >= this difference of their indices in the original array. If that is not the case, then unfortunately one can't squeeze in integral values in between them. 
- As a special case, if i is 0, that is it is first item in the LIS array, then it is mandatory that its value be > its index in the input array (your logic _does_ apply here)

​

1. 对于每个项，二进制搜索的最大项小于当前输入项，并且满足上面的point#1要求。我们总是可以像这样进行二进制搜索，因为如果前提是某个值，那么它递归地保存的所有值都小于当前所考虑的二进制搜索值。

我使用这种方法通过测试用例。

编辑：添加更多解释，因为注释部分不允许冗长的注释。

详细解释

让LIS[]成为我们维护的LIS。然后，在对所有 Dosas进行处理后，最终答案=N- size(LIS)。

现在，我们面临的挑战是找到如何创建和维护这个数组-> LIS，这太有效了。它可以在O(N^2)中完成，但是对于一个大的N，可能会有10^6的值。

建议书

我提出以下不变式：

设LISi =2-元组(对)，其中含有Dosa的价格仅为(最小可能值)高于LISi-1处的Dosa值，且其在LISi-1处与Dosa的“指数差”小于或等于在LISi-1处的“价差”。

也就是说，if: LISi-1 =对(a，b)，其中a= Dosa的值和b=原始输入数组中的索引。

因此，下列各点必须保持不变：

如果LISi =对(u，v)，其中u= Dosa的值和v=原始输入数组中的索引

那么，以下内容应该始终正确：

1. U>a(即LISi中Dosa的价格必须严格大于LISi-1处的Dosa值.)为什么？好吧，这就是我们首先想要的，不是吗？严格递增的子序列)
2. U-a≥v-b(现在，您可能需要考虑一下为什么这必须保持)

考虑一个矛盾。假设u-a

现在，上述属性为二进制搜索提供了很好的条件。为什么？在尝试将当前正在考虑的Dosa与其(Dosa值，原始数组索引)对值(例如(u，v) )在某一位置的LIS中匹配时，我们必须具有：

1. 当前Dosa值>u(因为我们希望严格增加子序列)
2. 它们的指数之间的差异应小于或等于它们的Dosa值之间的差异(如上文#2所述)。

如果这一点不成立，那么我们确信以下任何一项都是正确的：

1. 当前的Dosa值≤u或，
2. 当前Dosa与Dosa在二进制搜索位置(v值)的指数差<它们各自的Dosa值差

如果是#1，那么我们显然需要在二进制搜索中搜索左边的分区(因为我们向右走得太远了)

如果它是#2，那么即使当前的Dosa值> u，那么即使向右，假设二元搜索项的Dosa值是u+ Delta，那么它的高度必须至少为v+ Delta，因此它不可能通过继续向右移动而产生指数差<=高度差。因此，我们必须停止并在左分区中搜索。

暂停。如果还不清楚的话再读一遍

编辑：扰流板-添加工作代码(滚动到打开)

对不起，我无法在这里添加代码，除非收到“您的帖子显示包含未正确格式化的代码”错误。所以，放置ideone.com链接

这里的示例代码：http://ideone.com/tPkUWk 编辑:我不想破坏别人的利益，所以我把代码变成了私有的。