HJ115 小红的区间构造：贪心+分类讨论破解数组构造难题

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，所以区间和不可能小于区间长度。例如n=3, l=2, r=3, s=1，区间长度为 2，区间和不可能做到 1，直接-1。

第二个无解条件：t < n。全局每个数至少是 1，总和不可能小于数组长度。这个直观，但很多选手在构造时容易忽略——他们脑子里已经在填大数了，忘了“最小也得是 1”这条底线。

这两个条件本质上都是“下界超限”。我习惯在做任何构造题时，先把所有变量能取的最小值算出来，再算最大值。最小值都不满足，后面代码写得再漂亮也没用。

2.2 全局余量和区间余量必须匹配

第三个无解条件来自两个额外量的比较。回到前面的定义：

• addIn = s - L
• addAll = t - n

如果addIn > addAll，说明全局给到 n 以后剩下的余量，连区间内需要的额外量都覆盖不了，必然无解。

举个例子：n=4, l=2, r=3, s=5, t=6。区间长度L=2，区间外个数M=2。区间内额外需要5-2=3，而全局额外只有6-4=2。就算区间外两个元素都只填 1，全局总和也已经达到 5+2=7，大于题目给的 6。所以无论怎么构造都失败。

这个条件比单纯的t >= s更精确。很多人以为只要总和大于区间和就能行，其实还必须扣除每个位置的基础 1。你可以把“每个位置基础 1”想象成房租，先把房租交了，剩下的才是可支配收入，可支配收入不够局部目标就是无解。

2.3 区间覆盖全数组时，必须要求总和等于区间和

第四个无解条件最容易被忽略：当区间覆盖了整个数组，也就是L == n时，区间外个数M = 0。这时候没有外部位置可以吸收addAll - addIn，所以必须addAll == addIn，也就是s == t。

比如n=4, l=1, r=4, s=7, t=10。区间长度等于 4，整个数组都是区间内。区间和是 7，总和却是 10，这两个值不可能同时满足，因为所有元素都被同一个区间约束。你让区间和变成 7，总和就必然是 7；让总和变成 10，区间和也必然是 10。

这个问题和“没有区间外水箱”的本质等价。很多代码不特判会直接数组越界，或者输出一个一看就错的答案。我最早写的时候，因为没处理这个分支，白白找了一晚上 bug。

判断条件汇总如下：

3. 构造方案与代码实现，给两种分法

3.1 极简构造法：全填 1，再定向补差

无解判断做完后，构造其实简单到令人发指。步骤如下：

1. 先把答案数组全部初始化为 1。
2. 在区间内任意找一个位置，加上addIn。
3. 在区间外任意找一个位置，加上addAll - addIn。
4. 输出整个数组。

为什么这样一定正确？因为区间内其他位置保持 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。base=1, rem=2，于是三个位置分别加 2、2、1，总和正好加 5。这种分配法不会改变约束关系，只是让输出数据看起来更“正常”。

均匀分配法的另一个好处是方便检查溢出：如果total很大，分布到多个位置后单个元素值不会太离谱。不过只要用了long long，基本也稳。

3.3 C++ 完整实现

#include <bits/stdc++.h> using namespace std; using int64 = long long; void distribute(vector<int64>& 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; } vector<int64> 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 手工推演一组样例

我拿一组常见样例推一遍：n=5, l=2, r=4, s=8, t=20。

此时L=3, M=2。初始全 1 的数组是[1,1,1,1,1]。addIn = 8-3=5，addAll = 20-5=15。addIn <= addAll，且M>0，可行。

区间内分配 5：我用均匀法，长度 3，base=1, rem=2，区间内变成 2、2、1，于是数组变成[1,2,2,1,1]，但区间下标对应的是索引 1、2、3，区间和是2+2+1=5，还没到 8。等等，这里我搞错了均匀分配的含义。

重新来：区间内长度 3，初始都是 1，要在三个位置上一共再加 5。base = 5 // 3 = 1，rem = 5 % 3 = 2。三个位置各加 1，前两个位置再额外加 1。所以三个位置的变化量是 2、2、1，最终区间内元素是[3,3,2]。正确。

区间内完成后数组为[1,3,3,2,1]，区间和是3+3+2=8，正好。剩余rest = 15-5=10，找到第一个区间外下标，索引 0 不在区间[2,4]内，于是a[0] += 10，得到[11,3,3,2,1]。总和是11+3+3+2+1=20，区间和依然是 8。答案合法。

如果不做均匀分配，直接极简法也一样：区间内第一个元素加 5，[1,6,1,1,1]，区间和是 8；区间外加 10，[11,6,1,1,1]，总和是 20。也合法。所以构造题往往没有唯一答案，判题只关心约束是否满足。

4.2 我实战中踩过的高频坑

第一个坑是把剩余差值塞到数组第一个位置，但没判断这个位置是否在区间内。当l=1时，数组第一个位置就是区间内下标，加进去之后区间和直接被撑大。这个 bug 隐蔽在测试样例不覆盖l=1的时候，本地过了，提交才 WA。

第二个坑是漏判addIn > addAll。有几个样例长得特别有迷惑性，比如n=4, l=2, r=3, s=5, t=6，看起来 6 比 5 大，好像可行，实际上区间外至少还要放 2 个 1，全局最小已经是 7。这个案例非常适合写进题解，记住它就能避免同一类错误。

第三个坑是int溢出。如果n和t给到1e9甚至1e14，构造出来的某个元素可能是万亿级别的数字。我第一次用int存答案，一提交就错，改成long long立刻通过。刷题时养成习惯，看到求和、求区间，先想会不会超int。

第四个坑是全区间覆盖不特判。比如n=4, l=1, r=4，区间外不存在，代码里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 >= 0
• addAll >= 0
• addIn <= 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]，区间外放[L+1, L+2, ...]，这样天然不存在重复值。然后看区间和与全局和差了多少，把差值一次性加在某个“最大值”元素上，因为最大值本身已经很大，再加上去大概率不会撞到别的元素。

如果区间覆盖整个数组，情况更严格，但依然可以构造：让数组从 1 到 n 递增排列，然后把所有差值全部加到最后一个位置。只要差值非负且没有别的元素比它大，互异性就能保持。

从这道题延伸开去，你慢慢会发现，所有区间构造题的核心都是同一个套路：先把基础值铺好，再算局部和全局的差额，最后把差额定向塞到合适的桶里。判断条件越早列全，代码越短，越不容易错。我个人在实际做题中体会最深的一点是：构造题不要急着写循环，先在草稿纸上把最小情况推一遍，把无解分支列完，剩下的代码往往只是一次遍历的事。