变化最小不需要做阵列严格递增要做、阵列、不需、最小

2023-09-11 23:08:56 作者：你的路过我的错过/*

我有一个问题，我们有数字数组，我们必须让它严格通过零个或多个更改数组元素越来越多。

I have a problem in which we have an array of numbers and we have to make it strictly increasing by making zero or more changes to the array elements.

我们被要求使数组严格递增所需变化的最小数

We are asked the minimum number of changes required to make the array strictly increasing.

示例

如果阵列为1 2 9 10 3 15

if array is 1 2 9 10 3 15

所以ANS = 1，如果变3至12之间的一些数到14。

so ans=1 if change 3 to some number between 12 to 14.

如果1 2 2 2 3 4 5

if 1 2 2 2 3 4 5

ANS = 5

因为改变为2〜3，然后2-4然后3-5然后4-6然后5-7

since changing 2 to 3 then 2 to 4 then 3 to 5 then 4 to 6 then 5 to 7

约束：

在阵列LT元素的个数= 10 ^ 6

Number of elements in array <= 10^6

每个元素＆lt; = 10 ^ 9

Each element <= 10^9

注意：

这是不是一个功课，有人问我的采访，我无法给出一个算法吧。

This is not a homework, it was asked in my interview and I was unable to give an algorithm for it.

有人可以给我一个算法？

Can somebody give me an algorithm?

既然是迷你/最大的问题，所以它的声音动态规划给我，但我需要帮助。

Since it is mini/max problem, so it sounds dynamic programming to me, but I need help.

HINT 1

This is very close to the standard longest increasing subsequence problem which is solvable in O(nlogn).

如果你可以改变号码小数，那么答案将是相同的。（变化最小数=最长递增子字符串长度的长度）

If you could change the numbers to decimals then the answer would be identical. (Min number of changes = length of string-length of longest increasing subsequence)

不过，因为你需要在两者之间，你将不得不稍微修改标准算法不同的积分值。

However, as you need distinct integral values in between you will have to slightly modify the standard algorithm.

考虑一下，如果你做X更改数组会发生什么[我] = X [I] -i。

Consider what happens if you change the array by doing x[i]=x[i]-i.

您现在需要修改这个变化的阵列通过的最小数量的变化，使得每个元素的增加，或者保持不变。

You now need to modify this changed array by making the smallest number of changes such that each element increases, or stays the same.

您现在可以搜索最长不下降子序列在此数组，这将告诉你有多少元素可以保持不变。

You can now search for the longest non-decreasing subsequence in this array and this will tell you how many elements can stay the same.

不过，这仍然可以使用负整数。

However, this may still use negative integers.

一个简单的方法来修改算法只使用正数是数组的开始追加了一大堆数字。

One easy way to modify the algorithm to only use positive numbers is to append a whole lot of numbers at the start of the array.

即。改变1,2,9,10,3,15至-5，-4，-3，-2，-1,1,2,9,10,3,15

i.e. change 1,2,9,10,3,15 to -5,-4,-3,-2,-1,1,2,9,10,3,15

然后你就可以确保最佳的答案永远不会决定要1去负的，因为它会花费这么多，让所有负数较小。

Then you can be sure that the optimal answer will never decide to make the 1 go negative because it would cost so much to make all the negative numbers smaller.

（你也可以修改最长递增序列算法有额外的限制，但是这可能是很难$ C $正确的面试情况。C）

(You can also modify the longest increasing subsequence algorithm to have the additional constraint, but this might be harder to code correctly in an interview situation.)

在最初的例子在此之后通过：

Following this through on the initial example:

原始序列