桩的博弈

Question

最近，我遇到了一个似乎相当有趣的游戏，它建议在大型数据集上实现双指针和前缀和技术。以下是任务本身：

假设有一个长度为k的数组v，其中k (k<=10**5)表示由两个数字组成的条目数量:a(所谓的桩)和N(数量)，例如：

k = 3
v = [[2, 2], [3, 2], [2, 1]]

A (v[i][0])是值，N (v[i][1])是给定值的次数。换句话说，N是A的频率。

现在，我们要做的是选择最小A，从列表的两端开始，从当前的位置减去它，并将它添加到下面的位置。然后，我们继续这样做，在中间只剩下两到一次尝试。换句话说，每一步我们选择最小的一堆，并从两端减去它，直到剩下一或两堆。

答案应该包括两行:第一行包含“1”或“2”，这取决于剩余的堆数，第二行是结果本身。

为了简化，我们可以将成堆表示为如下所示的简单列表：

v = [2, 2, 3, 3, 2] 

我们从左端和右端选择最小值(2)，减去它并添加到下一个值：

v = [0, 4, 3, 5, 0]

最小的4和5是4，所以我们减法4，得到两堆。

v = [0, 0, 11, 1, 0]

产出如下：

2
11 1

我的代码是：

k = int(input())
a = []
for _ in range(k):
    A, N = map(int, input().split())
    x = [A] * N
    a += x


l = 0
r = len(a)-1
while r - l > 1:
    s = min(a[l], a[r])
    a[l] -= s
    a[r] -= s
    a[l+1] += s
    a[r-1] += s
    if a[l] == 0:
       l += 1
    if a[r] == 0:
       r -= 1

if a[r] == 0 or a[r]==a[l]:
    print(1)
    print(a[l])
      
else:
    print(2)
    print(a[l], a[r])

该解决方案在k= 10**5的时间限制(2秒)失败，因为它需要将数组转换为普通列表，而且几乎不使用前缀和。我确信，有一个更快的解决方案，前缀和，额外的变量和存储数组的给定。如果有任何关于如何加快代码速度的建议，我将不胜感激。

为了防止任何与语言相关的评论:游戏是为任何编程语言提供的，所以时间限制不是python的具体问题。

Answer 1

我不会给你答案，但我会给出合理的答案。

关键不在于算法执行得更快，而是在于找出在减少工作量的同时应用该算法的结果。为了使这更容易，我将用一个更慢的算法来代替这个算法，而这个算法恰好更容易推理。

与其从两边减去较小的部分，然后再加到下一边，不如从两边减去1，然后再加到下一边。所以你的例子应该从以下几个方面开始：

[2, 2, 3, 3, 2]
[1, 3, 3, 4, 1]
[0, 4, 3, 5, 0]
...

我们开始推理吧。

首先，假设我们在一端有A，那么需要采取多少步骤才能逐个推进这一步？答案就是简单的A。

如果A后面跟着k as会发生什么呢？在整个块中前进，直到最后一个元素被堆在一起

A + A+a + A+2a + ... A+(k-1)a
    = kA + (1 + 2 + ... + (k-1))a
    = kA + k(k-1)a/2

此时，最后一个元素现在有了A + ka元素。

所以，现在，在不扩展一个块的情况下，我们可以用一个简单的公式计算出需要多少工作才能通过它。我们也可以在另一边这样做。因此，在不扩张的情况下，我们可以开始消耗两边的整个区块，直到我们在最后的2或3个街区达到中间。然后，我们必须小心，但我们可以准确地确定一个是什么时候，另一方完成一个块。然后，我们可以将这些块分割成较小的块元素，并继续前进，直到我们在前进的前线之间找到最多3个阵列元素，它们将在其中相遇。然后，我们用原来的算法几次得到准确的答案。

但是你必须能够通过一个简单的算术计算来完成整个块，这样才能达到足够快的速度。

祝你好运，所有的边界条件都是正确的！