题目链接P17294 [ICPC 2026 Xian I] North and South - 洛谷思路先把“使元素相等”换成“使偏差为零”设最终所有元素都等于v。由于每次操作作用在偶数长度的区间上区间内1与-1各占一半总和不变。因此v 只能是平均值 sum / n 若 sum % n ! 0直接 -1于是令c[i] a[i] - v问题变为用同样的操作把c全部变成 0。这一步没有用到操作的细节只用到“总和不变”这一个守恒量。它把“所有元素相等”这个约束变成了一个更清楚的目标全零。第二次换描述不看c看它的前缀和在a或c上直接看这个操作是一团交替的1 -1很难处理。换一个视角P[k] c[1] c[2] … c[k]只看k 1 … n - 1稍后解释为什么不看n。关键引理一次操作[l, r]长度为偶数对 P 的影响是P[l]、P[l2]、P[l4]、…、P[r-1] 各加 1 其余 P 不变证明操作让c[i]增加(-1)^(i-l)。对P[k]的影响就是从l到min(k, r)的这部分求和Σ(il..min(k,r)) (-1)^(i-l) 1当 k-l 为偶数且 k ≤ r 0其余情况所以P[k]恰好在下标与l同奇偶、且不超过r时加一。这个引理的价值原本“给一串位置交替加一减一”现在变成了给“同奇偶的一段连续下标”同时加一。这就是最经典的“区间加一”模型。问题的形态完全变了。由引理立刻得到两个结论结论一P[k]只会增加不会减少每次操作对每个P[k]要么 1要么不动没有减小的可能。而目标要求所有P[k] 0。因此若初始存在某个 P[k] 0 → 永远回不到 0 → -1这就是程序里那句“前缀和超过允许值就无解”的真正含义P[k] (a[1]…a[k]) - k·v P[k] 0 ⟺ a[1]…a[k] k·v结论二P[n]恒为 0P[n] sum - n·v 0天然成立。而操作也改不动它——偶数长度的区间内1与-1相抵总和不变。所以k只需要走到n - 1。如果硬把k n也算进去得到的需求是n·v - sum 0加不加都是零只是白算一次。计数把需求画成一排柱子令t[k] -P[k] k 1 … n-1含义是位置k还需要被覆盖t[k]次。条件P[k] ≤ 0保证了t[k] ≥ 0。现在问题变成有一排柱子第k根高t[k]。 一次操作可以在“同一奇偶性的一条连续区间”上叠一层。 求最少操作次数。为什么奇偶两类互不相干由引理一次操作动的是下标l, l2, …, r-1它们与l同奇偶。也就是说起点 l 为奇数 → 只影响奇数下标的 t 起点 l 为偶数 → 只影响偶数下标的 t没有任何一次操作能同时改动两类。两类之间既不共享操作也不共享约束因此可以分别求解最后把次数相加。代码里用两个变量分别记录这两条“水位线”long long dx[2] {0, 0}; int par k 1;单类的最少操作数只看“上升”对单独一类按位置顺序扫描维护“上一层的高度”高度上升手里没那么多层可用必须新开t[k] - t[k-1]条高度下降多出来的层在这一格结束即可不用花钱。就是看最多有几层可以同时进行变化因此答案 Σ max(0, t[k] - t[k-1]) 同一类内t[0] 0两个例子例一5 4 3 2 1开 5 条第 1 层盖 1~5第 2 层盖 1~4… 第 5 层盖 1一共 5 条每条都是连续的一段。5 0 0 0 0 55 4 3 2 1 后4个都可以跟随5一起变动完例二5 1 2 3 4第 1 格要 5 层 → 开 5 条 第 2 格只要 1 层 → 4 条到此为止免费 第 3 格要 2 层 → 手上只剩 1 条必须新开 1 条 第 4 格要 3 层 → 新开 1 条 第 5 格要 4 层 → 新开 1 条不连续导致中间的先满足条件导致链断裂需要重新开始计算5 0 1 1 1 8所以第二个答案是 8不是 5。“掉下去再爬上来”的每一段爬升都要付钱——柱子断开之后原来的长条无法再接回去。完整思路一、读入求 sum 二、若 sum % n ! 0 → -1 三、v sum / n 四、按位置扫 k 1 … n-1 P a[k] - v 注意这里是 1-indexed 的 a[k] t -P 若 t 0 → -1 与同类上一格比较累加增量 五、输出累计值代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin t; while (t--) { int n; cin n; vectorlong long a(n 1); long long sum 0; for (int i 1; i n; i) { cin a[i]; sum a[i]; } if (sum % n ! 0) { cout -1 \n; continue; } long long v sum / n; long long P 0, ans 0; long long dx[2] {0, 0}; bool ok true; for (int k 1; k n; k) { P a[k] - v; // P[k] long long need -P; if (need 0) { ok false; break; } int par k 1; if (need dx[par]) ans need - dx[par]; dx[par] need; } cout (ok ? ans : -1) \n; } return 0; }补充底层数组究竟是怎么变的前面几节都在P上讨论容易让人产生一个疑问“那a本身是怎么变的”两者不是两套算法而是同一串操作的两种记法看a看P一段区间上交替1 -1 1 -1同奇偶的一段下标各1变化杂乱看不出规律一根横条盖一层层次分明一个完整的例子取a [0, 0, 1, 3]则v 1c [-1, -1, 0, 2]P [-1, -2, -2]即t [1, 2, 2]。公式给出的答案是 4 步。下面把 4 步全部写出来同时记录a、c、P的变化。初始a: 0 0 1 3 c: -1 -1 0 2 P: -1 -2 -2第 1 步操作[1, 4]a上1 -1 1 -1a: 1 -1 2 2 c: 0 -2 1 1 P: 0 -2 -1 P[1]、P[3] 各 1第 2 步操作[3, 4]只动第 3、4 格a: 1 -1 3 1 c: 0 -2 2 0 P: 0 -2 0 只有 P[3] 1第 3 步操作[2, 3]a: 1 0 2 1 c: 0 -1 1 0 P: 0 -1 0 只有 P[2] 1第 4 步再次操作[2, 3]a: 1 1 1 1 c: 0 0 0 0 P: 0 0 0四步结束所有元素相等。核对这四次操作在P上分别做了[1,4] → P[1] 1P[3] 1 [3,4] → P[3] 1 [2,3] → P[2] 1 [2,3] → P[2] 1合计P[1]1 次 -1 → 0 P[2]2 次 -2 → 0 P[3]2 次 -2 → 0不多不少恰好补平。结论a的变化看起来是“交替加减”很乱但在P上每一次操作就是一根横条盖住了哪几个位置一目了然。P不是抽象记号而是a变化的账本——每一笔都能对上具体某一次操作。正因为这笔账一一对应才可以只在P上做优化而不必回到a上去模拟。