企业官网建设流程全解析

今天继续打卡信奥刷题，这是系列第2942篇。这次要做的是洛谷P5847，题目名“mea”，源自IOI 2005。看到这个英文名，很多新手第一反应是“这啥单词”，其实它就是“mean”的变体，考的是平均值约束建模。说实话，这道题如果没接触过差分约束，会走很多弯路；但一旦想通“前缀和之差表示区间平均值”这个点，整道题就变成了一张裸的最长路图，剩下的就是C++实现问题了。这篇文章适合两类人看：一是准备NOIP/省选的选手，可以把这道题当成差分约束的典型练习；二是刚学图论想挑战IOI原题的朋友，看看国际赛场当年是怎么变着花样考基础模型的。

1. 整体思路：先看题目在说什么

1.1 把题面翻译成“人话”

原题题面很绕，我直接说核心：有一个长度为n的整数序列a，每个位置上的数都有下限和上限，要满足给出的m个区间约束。每个约束说的是某个连续子段内的平均值（mean）恰好等于一个给定值，或者不小于/不大于某个给定值。最后让你求出整个序列和的最小值或最大值，如果无解就输出对应标记。题目名里的“mea”就是mean，所有约束都围绕平均值展开。

这类问题乍一看像二分答案+贪心，因为“平均值”看起来有连续性，可以用实数二分去逼近。但你仔细想，这里有多个约束，还要满足每个位置的范围。如果去二分平均值，每次check都要处理一堆区间关系，容易写成大常数二分，而且对整数值域处理起来特别麻烦。IOI原题故意把n和m都放得很大，就是希望选手想到更本质的数学建模。

1.2 核心突破点：把所有平均值变成前缀和的差

设前缀和数组S，其中S[0]=0，S[i]=a[1]+...+a[i]。那么对任意区间[l,r]（下标从1开始），它的平均值可以写成：

mean(l,r) = (S[r] - S[l-1]) / (r-l+1)

如果题目要求这个平均值等于v，那么乘过去就得到一个等式：

S[r] - S[l-1] = v * (r-l+1)

如果要求平均值不小于v，则：

S[r] - S[l-1] ≥ v * (r-l+1)

这就是标准的线性不等式，恰好是差分约束系统能处理的形态。加上每个位置的值范围，比如L[i] ≤ a[i] ≤ R[i]，用前缀和表示：

L[i] ≤ S[i] - S[i-1] ≤ R[i]

这同样是不等式组。所以整道题就是给你一组形如“x_u - x_v ≤ w”或“x_u - x_v ≥ w”的约束，求x_n - x_0的最小值/最大值。到这里，思路已经清晰了一半。

1.3 为什么用差分约束而不是其他算法

有些同学会想到线性规划或单纯形，但竞赛环境不现实；还有些同学想用“平均值不等式+斜率优化”，但那是针对单个区间的最大平均值，这里多个区间之间会互相牵扯，没法直接套。差分约束的优势在于：它把不等式组转成图上的最短路/最长路问题，复杂度是O(nm)级别的SPFA，虽然理论上不是最优，但配上优化后能过IOI的数据。而且这道题建出来的图边数只有O(n+m)，SPFA在稀疏图上跑得飞快。

另一个隐蔽的好处是，差分约束天然能处理“无解”的情况——只要图里出现正环（最长路）或者负环（最短路），就说明约束之间存在矛盾。这一点用二分答案很难做得干净。

2. 核心细节：不等式转换与建图方向

2.1 所有不等式统一成“差不超过”

差分约束最常见的写法是把所有不等式整理成x[u] - x[v] ≤ w的形式，然后从v向u连一条边权为w的有向边，跑最短路，得到的是x的最大差值。但我们这里既有等号又有“≥”，还有求最小值/最大值，怎么统一？

我的习惯是先确定目标：如果题目要求的是“总和的最小值”，那么对应的就是S[n] - S[0]的最小值。怎么求？直接把所有不等式转成“≥”的形式，跑最长路。因为最长路的松弛条件是dist[v] < dist[u] + w，它天然维护的是每个变量的下界。把所有“≥”形式的约束建成有向边，跑出来的dist就是满足所有下界约束的最小可行解。最后答案就是dist[n] - dist[0]。具体的边方向如下：

• 若 S[r] ≥ S[l-1] + V_const，则从 l-1 到 r 连一条权值为 V_const 的边。
• 若 S[l-1] ≥ S[r] - V_const，则从 r 到 l-1 连一条权值为 -V_const 的边。
• 若等式成立，则这两条边都要连。

这里的关键是：最长路跑出来的是“最小下界”的一组解。换句话说，在满足所有“S[i]至少是多少”的约束下，dist[i]被推到刚刚好满足下界的位置。因此dist[n] - dist[0]就是S[n]所有可能取值中的最小值。

2.2 值域上下界怎么进图

位置范围约束 L[i] ≤ a[i] ≤ R[i] 即：

L[i] ≤ S[i] - S[i-1] ≤ R[i]

拆成两个不等式：

S[i] ≥ S[i-1] + L[i] => 从 i-1 到 i 连权值为 L[i] S[i-1] ≥ S[i] - R[i] => 从 i 到 i-1 连权值为 -R[i]

这其实是两条“基础边”，正好对应最长路的松弛方向。如果L和R都是常数，那么图里天然存在一条从头到尾的链条，不会出现孤立点。这也是为什么能用差分约束求S[n]的原因——即使没有区间约束，位置范围也限制了前缀和的斜率。举个例子，如果L[i]=1，R[i]=100，那么S[i]必须比S[i-1]至少大1，同时S[i-1]必须比S[i]至少大-100，这就在相邻前缀和之间形成了一个“走廊”。

2.3 起点和终点的处理

我们的源点自然是S[0]，它必须有一个初始值。差分约束里，如果没有额外限制，所有变量的值可以整体平移，所以S[0]取0即可。但题目可能要求a[i]是正整数（下限是1），那S[0]=0也就自然固定。注意S[0]固定后，S[i]的取值范围就会被链条限制住。如果某个约束要求S[n]很大，而0到n之间被中间点的上下限卡住，就可能无解，这正是SPFA判正环能捕捉到的矛盾。

还有一个容易忽略的点：如果题目没有显式给出每个位置的上下限，不要以为就不用连边了。很多差分约束题默认所有变量可以取任意整数，但那样会导致图不连通，SPFA从源点出发无法覆盖所有点，结果自然不对。所以遇到这类题，第一件事就是检查“每个变量的取值范围”是否给了；没给的话，要么加虚拟源点连零边，要么自己补上-INF到INF的约束。P5847里是明确给了范围边的，这也是它比纯模板题稍微复杂的原因。

2.4 等号约束的拆分技巧

区间平均值等于v是等式，等价于两个不等式：

S[r] - S[l-1] ≥ w S[r] - S[l-1] ≤ w

第二个不等式取负号变成：

S[l-1] ≥ S[r] - w

于是得到两条边。很多人写代码时只连第一条，忘了反向边，导致跑出来的dist[n]偏大或偏小，样例都过不了。这里有个验证方法：自己随机造几个小数据，用暴力枚举a序列来对拍。如果对不上，优先检查等号是不是拆了两条边。

2.5 无解时正环如何产生

差分约束无解的本质是存在矛盾环。比如约束S[3] ≥ S[0]+6，同时S[0] ≥ S[3]-4，这就会形成一个环0->3权6，3->0权-4，总权2>0，是正环。跑最长路时，每绕一圈dist[0]都会增加2，永远松弛不完，于是我们判定有正环。P5847里的区间约束和值域范围叠加，很容易构造出这种矛盾。例如区间[1,3]平均值至少2，加上每个位置最大只能填1，那么就要求S[3]-S[0]≥6，但每个位置最大1最多只有3，于是约束冲突。这种冲突最终会在图上形成一个正环。

3. 实操过程：C++实现与代码讲解

3.1 数据结构选择

这道题的边数包括：每个位置两条范围边，加上每个区间平均值的两条边，总边数不超过2(n+m)，点数不超过n+1。用vector存邻接表就够了，但追求性能的话可以用链式前向星。我偏爱链式前向星，因为遍历快，而且写起来不依赖STL的分配器。结构体定义：

struct Edge { int to, next; long long w; } edge[MAXE * 2]; int head[MAXN]; int ecnt; void addEdge(int u, int v, long long w) { edge[++ecnt] = {v, head[u], w}; head[u] = ecnt; }

这里的w是long long，因为平均值乘以长度后可能超过int，前缀和也能达到1e6 * 1e5 = 1e11级别，必须开long long。如果你用int，乘积溢出后会变成负数，跑出来的dist直接崩掉。

3.2 SPFA最长路模板

我们跑最长路，判正环。常规SPFA判负环是记录每个点入队次数，超过n就认为有负环；最长路对应判正环，同样是某个点松弛成功被推进队列的次数超过n，就说明存在正环。我写一个比较稳的版本：

const int MAXN = 100005; const long long INF = 1e18; int n, m; int cnt[MAXN]; long long dist[MAXN]; bool inq[MAXN]; bool spfa() { for (int i = 0; i <= n; ++i) { dist[i] = -INF; } queue<int> q; dist[0] = 0; q.push(0); inq[0] = true; while (!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].to; long long w = edge[i].w; if (dist[v] < dist[u] + w) { dist[v] = dist[u] + w; if (!inq[v]) { q.push(v); inq[v] = true; if (++cnt[v] > n) { return false; } } } } } return true; }

注意：cnt[v]表示v被“成功松弛后入队”的次数，不是入队次数。判断条件用cnt[v] > n其实有点浪费，但稳妥。如果担心极端数据卡SPFA，可以换成Bellman-Ford，但IOI数据用SPFA一般能过，因为图是稀疏的有向图。如果想更稳，可以加SLF优化，后面会提到。

3.3 完整主流程：读入、建边、跑答案

主程序关键点：先读入n和m，再读入每个位置的L[i]和R[i]，同时连边。然后读入m个区间约束，每个区间有三个参数l,r,v。这里我们先假设每个约束是“平均值恰好等于v”来演示。连边：

int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) { long long L, R; scanf("%lld%lld", &L, &R); addEdge(i - 1, i, L); // S[i] >= S[i-1] + L addEdge(i, i - 1, -R); // S[i-1] >= S[i] - R } for (int i = 0; i < m; ++i) { int l, r; long long v; scanf("%d%d%lld", &l, &r, &v); long long w = v * (r - l + 1); addEdge(l - 1, r, w); // S[r] >= S[l-1] + w addEdge(r, l - 1, -w); // S[l-1] >= S[r] - w } if (!spfa()) { printf("-1\n"); return 0; } printf("%lld\n", dist[n] - dist[0]); return 0; }

如果题面是“平均值不小于v”，那第二个addEdge就不加，只加第一个。如果是“不大于v”，则只加反向边。原题我印象中同时有等于和不等于的混合，按上述方法拆分即可。这也是这类题唯一的“业务逻辑”转化点。

3.4 样例测试与边界检查

没有现成样例的话，我习惯自己造一个小数据验证。比如n=3，位置范围都是[1,100]，约束：区间[1,3]平均值为2。那么根据代码，建边有：

0->1权1，1->0权-100； 1->2权1，2->1权-100； 2->3权1，3->2权-100； 区间[1,3]平均值为2：0->3权6，3->0权-6。

跑最长路，dist[0]=0：

• 0->1权1：dist[1]=1；
• 1->2权1：dist[2]=2；
• 2->3权1：dist[3]=3；
• 0->3权6：dist[3]=max(3, 6)=6；
• 3->2权-100：dist[2]=max(2, 6-100=-94)不变；
• 3->0权-6：dist[0]=max(0, 6-6=0)不变。

最终dist[3]=6，S[3]-S[0]=6。a序列可以取[2,2,2]，平均值正好是2，和为6。输出dist[n]-dist[0]=6。看起来没问题。

但注意：dist[0]在极端情况下可能被更新成非0值。比如约束中存在S[0] ≥ S[3] - 2，而S[3]被推到很大时，dist[0]可能变大。这时候dist[n]-dist[0]仍然是正确的最小差值，但直接输出dist[n]就会错。所以主输出一定要写成dist[n]-dist[0]，而不是dist[n]。

3.5 读入优化与输出细节

如果n和m都到1e5，scanf足够，不需要手写快读。但如果数据量到1e6，建议用fread快读。我个人习惯封装一个：

inline long long read() { long long x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; }

输出方面，如果答案可能是负数？理论上S[n]-S[0]是序列和，如果位置范围允许负数，答案可能为负。原题一般限制为非负，但仍然要用long long输出，别用%d。

3.6 完整代码整合

把上面的片段拼起来，就是一份可直接交的代码。注意数组大小：head开到MAXN，edge开到MAXE，MAXE至少是2*(n+m)。我一般直接开成MAXN * 4，省心。SPFA里dist初始化为一个很小的负数，我用了-INF=1e18，如果边权绝对值很大，可以改成-0x3f3f3f3f3f3f3f3f。还需要在每次清空cnt和inq数组。

完整代码这里不重复贴了，只要按上面的思路组合即可。核心点都在，别漏掉反向边。

4. 常见问题与排查技巧实录

4.1 最短路还是最长路？方向总是搞反

这是差分约束平均类题目里最容易翻车的地方。我的经验是：不要背口诀，从“区间平均值 = v”出发手写公式，再决定连边。每一步问自己：这个不等式是“S[i] ≥ ...”还是“S[i] ≤ ...”。最长路的松弛条件是dist[v] < dist[u] + w，它天然维护的是下界。所以，所有形如“S[v] ≥ S[u] + w”的约束，都用u到v权为w的边。如果你跑出来答案很大，或者出现正环却认为无解，大概率是方向反了。一个快速验证方法是构造一个简单样例，比如n=1，范围[1,1]，约束平均值1。期望输出1。如果跑出-1或大数，就把所有边反向再试。

4.2 SPFA判环的cnt计数要放在哪个位置？

我见过很多同学把cnt[v]++放在if块外面，导致源点连入队几次就误判无解。正确逻辑是：只有当节点v因为松弛成功而被第一次加入队列时，才增加计数；如果它已经在队列里，即使又松弛了，也只是更新dist，不再push，计数也不变。这样才能真实反映“松弛成功导致入队”的次数。还有一种写法是用一个数组记录每个点累计松弛次数，每次松弛成功就++vis[v]，判vis[v] >= n+1。两种都行，但注意区分。

4.3 边界：l-1会不会越界？

区间[l,r]必须满足1≤l≤r≤n，所以l-1最小是0，最大是n-1；r最大是n。所以前缀和下标范围是[0,n]，数组开n+2即可。但如果你把数组开成MAXN=100005，n又恰好是100000，没问题；如果n是100000，边数是2*(n+m)，m也可能达到100000，总的边节点都要开够。我习惯把head数组开到MAXN，edge数组开到MAXN*3，防止溢出。

4.4 平均值v可能是小数吗？

IOI题中给出的v通常是整数，这样平均数乘以长度后还是整数。如果v是实数，就得把边权变成浮点数，SPFA照样可以跑，但判环和答案都会出现精度问题。所幸原题v是整数，我们直接用long long乘法即可。注意v*(r-l+1)可能超过int，乘法时v和长度都必须是long long。

4.5 卡SPFA怎么办？

SPFA在差分约束上容易被精心构造的数据卡，但IOI数据不是专门卡SPFA的。如果担心，可以用SLF优化：当新元素v的dist小于队首时插到队首。代码：

if (!inq[v]) { if (!q.empty() && dist[v] > dist[q.front()]) q.push_back(v); else q.push_front(v); inq[v] = true; if (++cnt[v] > n) return false; }

不过，如果图有正环，SLF不会影响判断，只是常数更小。另一个优化是，初始化时把所有点都推入队列，而不是只从0出发。这样可以避免某些点因为初始阶段无法到达而漏判。但注意此时dist要全部初始化为0（或者-INF加虚拟源点），cnt计数仍然有效。

4.6 为什么输出是dist[n]-dist[0]，不是直接输出dist[n]？

因为S[0]作为变量可能不为0，尤其在加入虚拟源点后。dist[n]是相对虚拟源点的最长路，dist[0]可能也被更新。题目要求的是a序列的和，也就是S[n]-S[0]。如果S[0]不是0，直接输出dist[n]就错了。这个坑我踩过，后来在样例上测试发现：当约束允许S[0]被抬高时，dist[n]-dist[0]才是正确的最小下界。

5. 扩展：从mea看IOI题的套路

打卡到第2942道，我已经很少追求“一上来就AC”了，更多的是看一道题能带出多少知识盲区。P5847这道题，表面是IOI2005的旧题，内核却是差分约束系统里最经典的“前缀和建模法”。如果把它吃透，以后遇到“区间和”“区间平均值”“区间比值”这类约束，都能条件反射地想到S数组。我曾经在省选模拟里见到一道“给定若干区间的乘积范围求可行解”的题，也是用log把乘法转成加法，再套差分约束，原理一模一样。

还有一个细节想提一下：写代码前的数学推导一定要写在纸上，不要直接在电脑上乱试。这道题我一开始把“区间平均值不小于v”误写成“不大于v”，结果样例全部通过但提交WA，后来手写公式才发现反向边漏了一条。差分约束题对方向的敏感程度，不亚于网络流建模，宁可多花5分钟推公式，也不要凭空写边。

如果你是在校学生，建议把这题和另外几道经典差分约束题（比如POJ 1201、洛谷P5960）一起刷，效果更好。P5847的难点在于隐藏了“前缀和”这一层转换，一旦拆破，剩下的代码量其实就是个裸SPFA。能把一个看似复杂的IOI题拆成模板题，这才是刷题最爽的地方。最后再分享一个小技巧：当你在SPFA里看到dist被反复更新但不知道是不是正环时，别急着加优化，先打印每个节点的入队次数，如果某个节点入队次数超过了n+1还活着，那一定是正环，别怀疑自己。老老实实输出-1，然后去检查哪条约束写反了。就这样，下一题再见。