今天继续打卡信奥刷题这是系列第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]0S[i]a[1]...a[i]。那么对任意区间[l,r]下标从1开始它的平均值可以写成mean(l,r) (S[r] - S[l-1]) / (r-l1)如果题目要求这个平均值等于v那么乘过去就得到一个等式S[r] - S[l-1] v * (r-l1)如果要求平均值不小于v则S[r] - S[l-1] ≥ v * (r-l1)这就是标准的线性不等式恰好是差分约束系统能处理的形态。加上每个位置的值范围比如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(nm)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]1R[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权63-0权-4总权20是正环。跑最长路时每绕一圈dist[0]都会增加2永远松弛不完于是我们判定有正环。P5847里的区间约束和值域范围叠加很容易构造出这种矛盾。例如区间[1,3]平均值至少2加上每个位置最大只能填1那么就要求S[3]-S[0]≥6但每个位置最大1最多只有3于是约束冲突。这种冲突最终会在图上形成一个正环。3. 实操过程C实现与代码讲解3.1 数据结构选择这道题的边数包括每个位置两条范围边加上每个区间平均值的两条边总边数不超过2(nm)点数不超过n1。用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; } queueint 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 样例测试与边界检查没有现成样例的话我习惯自己造一个小数据验证。比如n3位置范围都是[1,100]约束区间[1,3]平均值为2。那么根据代码建边有0-1权11-0权-100 1-2权12-1权-100 2-3权13-2权-100 区间[1,3]平均值为20-3权63-0权-6。跑最长路dist[0]00-1权1dist[1]11-2权1dist[2]22-3权1dist[3]30-3权6dist[3]max(3, 6)63-2权-100dist[2]max(2, 6-100-94)不变3-0权-6dist[0]max(0, 6-60)不变。最终dist[3]6S[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都到1e5scanf足够不需要手写快读。但如果数据量到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开到MAXNedge开到MAXEMAXE至少是2*(nm)。我一般直接开成MAXN * 4省心。SPFA里dist初始化为一个很小的负数我用了-INF1e18如果边权绝对值很大可以改成-0x3f3f3f3f3f3f3f3f。还需要在每次清空cnt和inq数组。完整代码这里不重复贴了只要按上面的思路组合即可。核心点都在别漏掉反向边。4. 常见问题与排查技巧实录4.1 最短路还是最长路方向总是搞反这是差分约束平均类题目里最容易翻车的地方。我的经验是不要背口诀从“区间平均值 v”出发手写公式再决定连边。每一步问自己这个不等式是“S[i] ≥ ...”还是“S[i] ≤ ...”。最长路的松弛条件是dist[v] dist[u] w它天然维护的是下界。所以所有形如“S[v] ≥ S[u] w”的约束都用u到v权为w的边。如果你跑出来答案很大或者出现正环却认为无解大概率是方向反了。一个快速验证方法是构造一个简单样例比如n1范围[1,1]约束平均值1。期望输出1。如果跑出-1或大数就把所有边反向再试。4.2 SPFA判环的cnt计数要放在哪个位置我见过很多同学把cnt[v]放在if块外面导致源点连入队几次就误判无解。正确逻辑是只有当节点v因为松弛成功而被第一次加入队列时才增加计数如果它已经在队列里即使又松弛了也只是更新dist不再push计数也不变。这样才能真实反映“松弛成功导致入队”的次数。还有一种写法是用一个数组记录每个点累计松弛次数每次松弛成功就vis[v]判vis[v] n1。两种都行但注意区分。4.3 边界l-1会不会越界区间[l,r]必须满足1≤l≤r≤n所以l-1最小是0最大是n-1r最大是n。所以前缀和下标范围是[0,n]数组开n2即可。但如果你把数组开成MAXN100005n又恰好是100000没问题如果n是100000边数是2*(nm)m也可能达到100000总的边节点都要开够。我习惯把head数组开到MAXNedge数组开到MAXN*3防止溢出。4.4 平均值v可能是小数吗IOI题中给出的v通常是整数这样平均数乘以长度后还是整数。如果v是实数就得把边权变成浮点数SPFA照样可以跑但判环和答案都会出现精度问题。所幸原题v是整数我们直接用long long乘法即可。注意v*(r-l1)可能超过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被反复更新但不知道是不是正环时别急着加优化先打印每个节点的入队次数如果某个节点入队次数超过了n1还活着那一定是正环别怀疑自己。老老实实输出-1然后去检查哪条约束写反了。就这样下一题再见。