HJ115 小红的区间构造拿到题目时其实没必要被“区间构造”这四个字吓住。它本质上是一道贪心加分类讨论的题给你几个限制让你把数组造出来难点不在构造过程本身而在于先把可行域想清楚。我第一次做这道题时直接去模拟区间样例跑对了却一直WA。后来把区间内、区间外拆成两个独立部分一下就通了。这篇文章把推导、代码和雷区都整理出来适合正在刷构造题的选手参考。1. HJ115 小红的区间构造先看清题面在说什么1.1 题面还原成最小模型“小红”只是题面里常用的角色包装抽离之后题目大概率长这样给定长度为n的正整数数组要你构造并且给出四个约束——区间左端点l、右端点r、区间和s、整个数组总和t。要求构造出的数组满足[l, r]区间内所有元素之和等于s同时整个数组所有元素之和等于t如果不存在就输出-1。这里有个细节值得先说清楚数组元素默认是正整数也就是每个数最小是 1。这个“最小是 1”看起来不起眼却是整个题目的基石。很多同学上手就考虑“我随便放几个大数把总和凑够”然后直接把区间和给忘了。等你造完才发现区间外多塞的那些数改不掉区间内已经被撑爆了。如果你手里的原题参数名和我这里不完全一样别急只要本质是“全局和 局部和”的构造这套思路直接平移就行。题目里的角色名、变量名都是包装数学结构才是核心。1.2 突破口把区间内和区间外当成两个独立水箱我先定义两个基础量区间长度L r - l 1区间外元素个数M n - L因为每个元素最小是 1所以整个数组的最小总和是n区间内的最小总和是L如果直接把数组全部填 1那么[l, r]的和就是L全局和就是n。这跟目标分别还有差距于是引入两个“额外量”addIn s - L区间内需要额外补的量addAll t - n全局需要额外补的量核心洞察是addAll这坨额外的数不是想放哪就放哪。为了让区间和满足s必须从addAll里分出addIn给区间内剩下的addAll - addIn只能放到区间外。区间内和区间外就像是两个水箱谁也不能把水倒进另一个水箱还要求水位不变。这个拆解法是所有解法的地基。你甚至可以不用数组直接在纸上推导只要确定addIn能被区间内吃掉剩下的能被区间外吃掉这道题就成立。2. 判断无解的四个边界条件先判无解再动手2.1 两个“最小值”约束最容易看漏第一个无解条件s L。区间内每个数至少是 1所以区间和不可能小于区间长度。例如n3, l2, r3, s1区间长度为 2区间和不可能做到 1直接-1。第二个无解条件t n。全局每个数至少是 1总和不可能小于数组长度。这个直观但很多选手在构造时容易忽略——他们脑子里已经在填大数了忘了“最小也得是 1”这条底线。这两个条件本质上都是“下界超限”。我习惯在做任何构造题时先把所有变量能取的最小值算出来再算最大值。最小值都不满足后面代码写得再漂亮也没用。2.2 全局余量和区间余量必须匹配第三个无解条件来自两个额外量的比较。回到前面的定义addIn s - LaddAll t - n如果addIn addAll说明全局给到 n 以后剩下的余量连区间内需要的额外量都覆盖不了必然无解。举个例子n4, l2, r3, s5, t6。区间长度L2区间外个数M2。区间内额外需要5-23而全局额外只有6-42。就算区间外两个元素都只填 1全局总和也已经达到 527大于题目给的 6。所以无论怎么构造都失败。这个条件比单纯的t s更精确。很多人以为只要总和大于区间和就能行其实还必须扣除每个位置的基础 1。你可以把“每个位置基础 1”想象成房租先把房租交了剩下的才是可支配收入可支配收入不够局部目标就是无解。2.3 区间覆盖全数组时必须要求总和等于区间和第四个无解条件最容易被忽略当区间覆盖了整个数组也就是L n时区间外个数M 0。这时候没有外部位置可以吸收addAll - addIn所以必须addAll addIn也就是s t。比如n4, l1, r4, s7, t10。区间长度等于 4整个数组都是区间内。区间和是 7总和却是 10这两个值不可能同时满足因为所有元素都被同一个区间约束。你让区间和变成 7总和就必然是 7让总和变成 10区间和也必然是 10。这个问题和“没有区间外水箱”的本质等价。很多代码不特判会直接数组越界或者输出一个一看就错的答案。我最早写的时候因为没处理这个分支白白找了一晚上 bug。判断条件汇总如下场景条件说明区间下界s L区间内最小和超限全局下界t n全数组最小和超限余量不足addIn addAll局部需求超过全局余量全覆盖L n s ! t没有区间外位置吸收余量3. 构造方案与代码实现给两种分法3.1 极简构造法全填 1再定向补差无解判断做完后构造其实简单到令人发指。步骤如下先把答案数组全部初始化为 1。在区间内任意找一个位置加上addIn。在区间外任意找一个位置加上addAll - addIn。输出整个数组。为什么这样一定正确因为区间内其他位置保持 1只有选中的那个位置加了addIn所以区间和是L addIn s。全局来看所有位置基础 1 的总和是n再加上addIn和addAll - addIn总和就是n addAll t。两个约束都精确匹配。难点反而在找“区间外任意一个位置”。如果你随手选了数组下标 0但区间是从 1 开始的那你就把额外的差值加进了区间内部区间和会被撑大答案就错了。正确做法是写一个函数从左到右找第一个不属于[l, r]的下标。这种极简构造法产生的数组可能很夸张比如把 10 亿全塞到一个位置上。但算法题只要没有值域上限限制这完全合法。构造题经常不追求“数值美观”而是追求“约束成立”。3.2 均匀分配法让输出更好看如果不想让某个位置单独扛下所有差值可以用“尽量均匀”的方式把差值分摊到区间内或区间外。基本思路是对于一段长度为cnt、需要增加total的连续区间基准增量base total / cnt剩余增量rem total % cnt先给每个位置加base再给前rem个位置额外加 1比如区间内长度为 3需要加 5。base1, rem2于是三个位置分别加 2、2、1总和正好加 5。这种分配法不会改变约束关系只是让输出数据看起来更“正常”。均匀分配法的另一个好处是方便检查溢出如果total很大分布到多个位置后单个元素值不会太离谱。不过只要用了long long基本也稳。3.3 C 完整实现#include bits/stdc.h using namespace std; using int64 long long; void distribute(vectorint64 a, int start, int cnt, int64 total) { if (total 0) return; int64 base total / cnt; int64 rem total % cnt; for (int i start; i start cnt; i) { a[i] base; } for (int i start; i start rem; i) { a[i] 1; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int64 n, l, r, s, t; cin n l r s t; int64 L r - l 1; int64 M n - L; int64 addIn s - L; int64 addAll t - n; if (addIn 0 || addAll 0 || addIn addAll) { cout -1 \n; return 0; } if (M 0 addIn ! addAll) { cout -1 \n; return 0; } vectorint64 a(n, 1); // 区间内补差值 distribute(a, l - 1, L, addIn); // 找第一个区间外位置 int outPos -1; for (int i 0; i n; i) { if (i l - 1 || i r) { outPos i; break; } } // 区间外补剩余差值 int64 rest addAll - addIn; if (outPos ! -1) { a[outPos] rest; } for (int i 0; i n; i) { if (i) cout ; cout a[i]; } cout \n; return 0; }这里distribute接受的是起始下标和长度调用时传l - 1和L正好覆盖区间内所有下标。区间外找位置时用i l - 1 || i r因为数组下标从 0 开始区间[l, r]对应下标[l-1, r-1]所以区间外的判断是i l - 1或i r。如果outPos返回-1说明找不到区间外位置那就是全覆盖情况已经在前面判掉了。代码不会走到这里但我还是保留了判断防止以后改题面时出事。3.4 Python 完整实现与自查函数def distribute(a, start, cnt, total): if total 0: return base, rem divmod(total, cnt) for i in range(start, start cnt): a[i] base for i in range(start, start rem): a[i] 1 def solve(n, l, r, s, t): L r - l 1 M n - L add_in s - L add_all t - n if add_in 0 or add_all 0 or add_in add_all: print(-1) return if M 0 and add_in ! add_all: print(-1) return a [1] * n distribute(a, l - 1, L, add_in) rest add_all - add_in out_pos -1 for i in range(n): if i l - 1 or i r: out_pos i break if out_pos ! -1: a[out_pos] rest print(*a)为了在本地快速验证我通常会写一个check函数def check(n, l, r, s, t, a): assert len(a) n assert all(x 1 for x in a) assert sum(a) t assert sum(a[l - 1:r]) s每次跑样例前先跑check至少能挡住 80% 的“以为对了其实错了”的情况。算法竞赛里构造题的提交失败往往不是逻辑有问题而是边界输出没对上一个断言能省很多时间。4. 实测运行与常见坑点盘点4.1 手工推演一组样例我拿一组常见样例推一遍n5, l2, r4, s8, t20。此时L3, M2。初始全 1 的数组是[1,1,1,1,1]。addIn 8-35addAll 20-515。addIn addAll且M0可行。区间内分配 5我用均匀法长度 3base1, rem2区间内变成 2、2、1于是数组变成[1,2,2,1,1]但区间下标对应的是索引 1、2、3区间和是2215还没到 8。等等这里我搞错了均匀分配的含义。重新来区间内长度 3初始都是 1要在三个位置上一共再加 5。base 5 // 3 1rem 5 % 3 2。三个位置各加 1前两个位置再额外加 1。所以三个位置的变化量是 2、2、1最终区间内元素是[3,3,2]。正确。区间内完成后数组为[1,3,3,2,1]区间和是3328正好。剩余rest 15-510找到第一个区间外下标索引 0 不在区间[2,4]内于是a[0] 10得到[11,3,3,2,1]。总和是11332120区间和依然是 8。答案合法。如果不做均匀分配直接极简法也一样区间内第一个元素加 5[1,6,1,1,1]区间和是 8区间外加 10[11,6,1,1,1]总和是 20。也合法。所以构造题往往没有唯一答案判题只关心约束是否满足。4.2 我实战中踩过的高频坑第一个坑是把剩余差值塞到数组第一个位置但没判断这个位置是否在区间内。当l1时数组第一个位置就是区间内下标加进去之后区间和直接被撑大。这个 bug 隐蔽在测试样例不覆盖l1的时候本地过了提交才 WA。第二个坑是漏判addIn addAll。有几个样例长得特别有迷惑性比如n4, l2, r3, s5, t6看起来 6 比 5 大好像可行实际上区间外至少还要放 2 个 1全局最小已经是 7。这个案例非常适合写进题解记住它就能避免同一类错误。第三个坑是int溢出。如果n和t给到1e9甚至1e14构造出来的某个元素可能是万亿级别的数字。我第一次用int存答案一提交就错改成long long立刻通过。刷题时养成习惯看到求和、求区间先想会不会超int。第四个坑是全区间覆盖不特判。比如n4, l1, r4区间外不存在代码里outPos会一直找不到返回-1。如果不处理后面a[-1]这种越界行为非常危险。我在 C 里用if (outPos ! -1)包住Python 里也得判断否则会改错元素。4.3 万能自查脚本直接在代码里加断言是最快的for _ in range(1000): n random.randint(1, 20) l random.randint(1, n) r random.randint(l, n) s random.randint(1, 100) t random.randint(1, 100) # 调用 solve 得到结果 # 如果结果不是 -1用 check 验证随机小数据能快速暴露“偶发”错误。构造题最怕就是手持一个样例觉得天衣无缝实际边界没覆盖到。我几乎每道构造题都会写这种随机验证跑一万组也不会花几秒但对正确性的信心提升是巨大的。5. 扩展值域限制、非负与互异要求5.1 如果题目加了值域上限原题如果额外要求每个数不超过某个值U判断就没那么简单了。此时区间内最多能容纳的额外量是L*(U-1)区间外最多能容纳的额外量是M*(U-1)。条件变成addIn 0addAll 0addIn L*(U-1)addAll - addIn M*(U-1)分配时同样用均匀法但要注意分配完不能超过U。更稳妥的写法是先算出每个位置最多还能加多少逐步塞。如果塞到某个位置时total还剩下但所有位置都到上限了那无解。这个变体在思路上仍然是“剩余量分别塞进两个水箱”只不过每个水箱有容量上限。编程时把容量上限也加入判断复杂度依然是O(n)。5.2 如果允许元素为 0很多衍生题会把“正整数”改成“非负整数”也就是最小值从 1 变成 0。此时判断逻辑反而更简单区间内基础最小值是 0所以addIn s - 0 s全局基础最小值是 0所以addAll t - 0 t需要满足s 0、t 0、s t全覆盖时依然要s t构造时数组先全部初始化为 0区间内补s区间外补t-s。看起来只是把 1 改成 0但很多选手会惯性沿用正整数版本的L和n导致偏移量算错。做题时一定要先看清楚题面说的是“正整数”还是“非负整数”。5.3 如果要求所有元素互不相同要求互异会更有挑战。常规解的思路是用一组“等差基底”占位比如区间内先放[1,2,...,L]区间外放[L1, L2, ...]这样天然不存在重复值。然后看区间和与全局和差了多少把差值一次性加在某个“最大值”元素上因为最大值本身已经很大再加上去大概率不会撞到别的元素。如果区间覆盖整个数组情况更严格但依然可以构造让数组从 1 到 n 递增排列然后把所有差值全部加到最后一个位置。只要差值非负且没有别的元素比它大互异性就能保持。从这道题延伸开去你慢慢会发现所有区间构造题的核心都是同一个套路先把基础值铺好再算局部和全局的差额最后把差额定向塞到合适的桶里。判断条件越早列全代码越短越不容易错。我个人在实际做题中体会最深的一点是构造题不要急着写循环先在草稿纸上把最小情况推一遍把无解分支列完剩下的代码往往只是一次遍历的事。