找到将所有元素转换为零的最小步骤

Question

给您一个大小为N的正整数数组。您可以选择任意正整数x，使x<=max(数组)从数组的所有元素中减去它，其大小大于和等于x。这个操作对于Ai>=x有一个成本Ai-x。一个特定步骤的总成本是和(Ai-x)。只有当和(Ai)小于或等于给定数K时，步骤才有效。对于所有有效步骤，请找到使数组中的所有元素为零的最小步骤数。 0<=i<10^5 0<=x<=10^5 0

有人能帮我找到什么方法吗？由于高度限制，DP将无法工作。

Answer 1

只是一些探索性的想法。

首先，应该对N有一个限制。如果N为3，则这比100容易得多。天真的蛮力方法将是O(k^N)

接下来，DP将无法处理这些约束，这是正确的。

对于一个贪婪的方法，我想要最小化不同的非零值的数量，而不是最大化我取了多少。我们的最坏情况方法是每次取最大一次，用于N步骤。如果你能得到两对条目的匹配，那么这就缩短了我们的方法。

如果可以的话，最明显的尝试就是一个搜索。然而，这需要一个下限(而不是上限)。我能看到的最天真的下限是ceil(log_2(count_distinct_values))。除非你非常幸运，而且这个问题可以很快解决，否则你的搜索范围不大可能有帮助。

我很好奇是什么使这个问题成为现实。

我确实有个主意。但要想让它发挥作用，还需要一些思考。天真地，我们希望为x选择每一个选择，并探索这种方式的路径。这是一个问题，因为x有x的选择。经过两个选择，我们有一个问题，而在3岁以后，我们肯定无法做到这一点。

但是，应该考虑数组元素的可能顺序(包括可能的和鼓励的)，以及可能做出的选择范围上的不平等。现在，我们不需要存储10^5选择的x，我们只需要存储我们得到的不同的顺序，以及在使我们达到目标的选择范围上存在哪些不等式。只要N < 10，如果我们聪明的话，弱序数是我们可以处理的东西。

不过，要充实这个想法，还需要做大量的工作。