问题重述 给定一个长度为 n 的整数序列 a，可以进行若干次操作，每次操作选择两个不同的下标 i 和 j，将 a_i 加 1，同时将 a_j 减 1。目标是使得前缀和之和等于后缀和之和，即： \[ \sum_{k=1}^n s_k = \sum_{k=1}^n t_k \] 其中： - \( s_k = a_1 + a_2 + \dots + a_k \)（前缀和） - \( t_k = a_k + a_{k+1} + \dots + a_n \)（后缀和） 要求求出最小的操作次数，如果无解则输出 -1。 初步分析 1. 前缀和之和与后缀和之和的关系： - 前缀和之和：\( S = \sum_{k=1}^n s_k = \sum_{k=1}^n \sum_{i=1}^k a_i \) - 后缀和之和：\( T = \sum_{k=1}^n t_k = \sum_{k=1}^n \sum_{i=k}^n a_i \) 可以证明 \( S = T \)： - \( S = \sum_{k=1}^n (n - k + 1) a_k \) - \( T = \sum_{k=1}^n k \cdot a_k \) - \( S = T \) 等价于 \( \sum_{k=1}^n (n - k + 1 - k) a_k = 0 \)，即 \( \sum_{k=1}^n (n - 2k + 1) a_k = 0 \) 2. 操作的性质： - 每次操作将 a_i 加 1，a_j 减 1，因此整个序列的总和 \( \sum_{k=1}^n a_k \) 是不变的。 - 我们需要调整 a 使得 \( \sum_{k=1}^n (n - 2k + 1) a_k = 0 \)。 3. 最小操作次数： - 每次操作可以看作是将一个单位的“值”从 a_j 转移到 a_i。 - 我们需要计算初始的 \( \sum_{k=1}^n (n - 2k + 1) a_k \)，然后通过操作将其调整为 0。 - 操作的最小次数等于需要调整的“值”的总量除以 2（因为每次操作可以调整 2 个单位，一个加一个减）。 解题步骤 1. 计算初始的 \( D = \sum_{k=1}^n (n - 2k + 1) a_k \)。 - 如果 D 不为 0，我们需要通过操作调整 a 使得 D 变为 0。 - 每次操作可以选择 i 和 j，将 a_i 加 1，a_j 减 1，因此 D 的变化量为： \[ \Delta D = (n - 2i + 1) \cdot 1 + (n - 2j + 1) \cdot (-1) = (n - 2i + 1) - (n - 2j + 1) = 2(j - i) \] - 每次操作可以调整 D 的值为 \( 2(j - i) \)。 - 为了将 D 调整为 0，我们需要找到一系列操作使得这些 \( 2(j - i) \) 的和等于 -D。 2. 最小操作次数： - 观察到每次操作的 \( \Delta D \) 是偶数（因为 \( 2(j - i) \)），因此如果初始 D 是奇数，则无解（输出 -1）。 - 如果 D 是偶数，我们需要找到最少的操作次数使得这些操作的 \( \Delta D \) 之和为 -D。 - 最优策略是每次尽可能调整最大的 \( \Delta D \)： - 最大的 \( \Delta D \) 是当 i = 1 和 j = n 时，\( \Delta D = 2(n - 1) \)。 - 最小操作次数是 \( \lceil |D| / (2(n - 1)) \rceil \)，但需要验证是否可以精确匹配。 3. 验证是否可以精确匹配： - 如果 D 是 0，则不需要操作（输出 0）。 - 如果 D 不为 0： - 如果 D 是 \( 2(n - 1) \) 的倍数，则操作次数为 \( |D| / (2(n - 1)) \)。 - 否则，需要检查是否可以分解为多个操作的组合。 结论 - 计算 \( D = \sum_{k=1}^n (n - 2k + 1) a_k \)。 - 如果 D 为 0，输出 0。 - 如果 D 不为 0： - 如果 D 是奇数，输出 -1（无解）。 - 如果 D 是偶数，输出 \( |D| / 2 \)（因为每次操作可以调整 D 的绝对值为 2 的倍数，最小操作次数是 \( |D| / 2 \)）。 代码实现 ```python n = int(input()) a = list(map(int, input().split())) D = 0 for k in range(1, n + 1): D += (n - 2 * k + 1) * a[k - 1] if D == 0: print(0) else: if D % 2 != 0: print(-1) else: print(abs(D) // 2) ``` 额外需要注意的逻辑点 1. 计算 D 时，k 的取值是从 1 到 n，因此 a 的索引是 k-1。 2. 每次操作可以调整 D 的绝对值为 2 的倍数，因此最小操作次数是 \( |D| / 2 \)。 3. 如果 D 是奇数，无法通过操作调整到 0，因此无解。 [2025-05-25 17:27:01 | AI写代码神器 | 1329点数解答]