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

Question

我正试图解决spojhttp://www.spoj.com/problems/DOSA这个问题，这也是一个采访的问题。
我的逻辑是从给定数组中获取满足[i]＞i（0的索引）的元素，因为其他元素总是需要改变的。
现在从这些选定的元素中找出严格递增的最长子序列，最后的答案是数组计算的初始长度
例子：
原始数组是：17 10 2 20 22
根据a[i]>i计算的新数组是17 10 20 22
现在，这个数组的LIS是5
所以，最终的答案是6-5=1
但它给出了错误的答案，任何人都能指出我的逻辑错在哪里。
编辑：
问题陈述：
拉利特要去吃晚饭，他面前摆着n个dosa，它们的价格用整数序列a1，a2，a3……an表示。
他决定用不同的方式吃饭。您可以用任何正整数替换任何dosa的价格。
必须替换多少个价格（整数）才能使生成的序列严格递增？
样本输入：
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直接应用于它（整个序列是严格递增的，并且在原始数组中只丢弃了一个[3]），那么它显然给出了1的答案。
接近
我的做法如下：
尝试建立LIS也就是说，保持数组a[i]，使得a[i]=到目前为止发现的递增子序列中的第i个最低项，该递增子序列也遵循这样的规律，即a[i]值的输入数组中其索引与a[i-1]的索引存在差异，从而：
它们各自的值之间的差异是>=它们在原始数组中的索引的差异如果不是这样的话，那么不幸的是，我们不能在它们之间挤压积分值。
作为特殊情况，如果i是0，即它是lis数组中的第一个项，那么它的值必须大于它在输入数组中的索引（您的逻辑在此适用）
对于每个项，二进制搜索小于当前输入项且满足上面第1点的最大项。一个人总是可以像这样进行二进制搜索，因为如果前提支持某个值，那么它递归地支持小于当前所考虑的二进制搜索值的所有值。
我用这种方法通过了测试用例。
[编辑]：添加更多说明，因为“注释”部分不允许详细注释。
详细说明
让LIS[]成为我们维护的LIS然后，在所有剂量处理完毕后，最终答案=n-大小（lis）
现在，问题归结为如何创建和维护这个数组->lis，这太有效了。它可以在O（N^2）中完成，但是对于一个较大的N，这将超时，值可能高达10^6我们将尝试在o（n*log（n））中解决它。
提案
我提出以下不变量：
设lis[i]=2元组（对），其中dosa的价格刚好（最小可能值）高于lis[i-1]的dosa的价格，并且其与lis[i-1]的dosa的“指数差”小于或等于与lis[i-1]的dosa的“价格差”
也就是说，如果：
LIS[i-1]=对（a，b），其中a=Dosa的值，b=其在原始输入数组中的索引
则必须保持以下状态：
如果LIS[i]=对（u，v），其中u=Dosa的值，v=其在原始输入数组中的索引
那么，以下内容应该始终正确：
u>a（即lis[i]中dosa的价格必须严格大于lis[i-1]中dosa的价值）。为什么？好吧，这是我们首先想要的，不是吗？严格递增的子序列）
u-a≥v-b（现在，您可能需要考虑一下为什么这必须成立）
考虑一个矛盾。比如说，u-a 那么在原始数组的索引b和索引a之间，就不可能唯一地适合dosa因为它需要至少一个重复的Dosa鸽洞原则。
现在，上面的属性非常适合二进制搜索为什么？
当试图将考虑中的当前dosa与它的（dosa值，原始数组索引）对值（例如，（u，v））匹配到某个位置的lis时，我们必须：
当前Dosa值>u（因为我们希望严格增加子序列）
其指数之间的差异应小于或等于其DOSA值之间的差异（如上文2所述）
如果这不成立，那么我们确信以下任何一项是正确的：
当前Dosa值≤u或，
当前Dosa与二进制搜索位置Dosa的索引差（值v）<各自的Dosa值差
如果它是#1，那么我们显然需要在二进制搜索中搜索左边的分区（因为我们向右走得太远了）
如果它是2，那么即使当前dosa值>u，那么即使向右，也可以说二进制搜索项的dosa值是u+delta，那么它的高度必须至少是v+delta，因此不可能通过继续向右，使索引差<=高度差。所以，我们必须停下来在左边的分区里搜索。
[暂停如果还不清楚，请重新阅读]
[编辑]：扰流器-添加工作代码（滚动以打开）
[抱歉，我无法在此处添加代码，除非出现“您的文章似乎包含格式不正确的代码”错误。所以，把ideone.com链接起来]
这里的示例代码： http://ideone.com/tPkUWk[编辑]：我不想破坏别人，所以我将代码设为私有代码。