我需要一种迭代数组的最佳方法

Question

我知道这是一个基于概念的网站，并且提出家庭作业类型的问题不受欢迎。因此，在我寻求帮助之前，先介绍一下我的背景：我是一名有竞争力的程序员，我将其作为我的爱好。

在最近的一次比赛中，我遇到了这个问题： https://atcoder.jp/contests/abc334/tasks/abc334_c

现在我用来解决这个问题的逻辑

这个问题可以认为是一个要求$\left\lfloor rac{K}{2}的问题 右 地板 $ 一双袜子，每种颜色 $A_1、A_2、\ldots、A_K$。 如果 $K$ 是偶数，则配对 $\left(A_1, A_2 右),\左(A_3, A_4 右), \ldots,\left(A_{K-1}, A_K ight)$，这样相邻的颜色（按排序顺序）就配对了，确实是这样。

问题出在 $K$ 为奇数时。在这种情况下，我们可以对唯一未配对的颜色进行暴力破解，可以找到与其他袜子配对的最佳方法，就像我们对偶数 $K$ 所做的那样。当唯一未配对的颜色固定后，剩余袜子配对时的最小总怪异度可以在 $O(N)$ 时间内天真地找到，但其结果是总共 $O\left(N^2 右）$ 复杂性。相反，当前几只袜子配对时，人们可以预先计算总的怪异程度，例如假设 $[2]=\left(A_2-A_1 右), \operatorname{presum}[4]=\left(A_4- 右.$ $\左.A_3 右)+\左(A_2-A_1 右）$，假设$[6]=\left(A_6-A_5 右)+\左(A_4-A_3 右)+\左(A_2-A_1 ight),\ldots$，以前缀和的方式；还可以找到“后缀和”。这样一来，总共可以在 $O(N)$ 时间内解决问题。

当我们使用这种方法并尝试解决问题时，由于问题的时间限制，我们会收到 TLE 错误。在检查社论时，摆脱此 TLE 的唯一方法是使用此优化：

当 $K$ 为奇数时，而不是暴力破解非奇数的袜子 配对后，只能尝试 $A_1, A_3, A_5, \ldots, A_K$ 。 在下面的示例代码中，我们采用这种方法来简化 实施。

我无法理解为什么不需要尝试 A2、A4 和所有其他甚至索引元素？有人可以帮助我或至少暗示这一优化背后的逻辑。谢谢你

编辑：我无法在这里修复我的乳胶，有人可以帮忙解决这个问题吗？我添加了我使用的算法的图像。无论我想用乳胶来解释什么。

Answer 1

假设您遗漏了一只偶数编号的袜子

x

。两侧的所有袜子（除了相邻的袜子）都必须与相邻的袜子配对，因此在

x

左右，您最终会遇到如下情况：

a x b

如果省略

x

，则必须将

a

和

b

配对，成本为

b-a

。如果您省略

a

或

b

，您总是会得到更好的结果，但成本为

x-a

或

b-x

。

...所以您永远不需要考虑遗漏偶数号码的袜子。

但是请注意，即使没有这种优化，您的算法也应该是线性时间的，并且考虑到问题中的约束，应该没有机会获得 TLE。