企业官网建设流程全解析

题目链接：

P17294 [ICPC 2026 Xi'an 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[l+2]、P[l+4]、…、P[r-1] 各加 1 其余 P 不变

证明：操作让c[i]增加(-1)^(i-l)。对P[k]的影响就是从l到min(k, r)的这部分求和：

Σ(i=l..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]恒为 0

P[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, l+2, …, 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 = 5

5 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; vector<long 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 = [0, 0, 1, 3]，则v = 1，c = [-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 -1）

a: 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] +1，P[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上去模拟。