GESP 2024年6月 真题题解 | 宝箱(编程基础)
- 2026-11-23 05:46:53
小杨发现了 n 个宝箱,其中第 i 个宝箱的价值是 aᵢ。
小杨可以选择一些宝箱放入背包并带走,但是小杨的背包比较特殊,假设小杨选择的宝箱中最大价值为 x,最小价值为 y,小杨需要保证 x-y≤ k,否则小杨的背包会损坏。
小杨想知道背包不损坏的情况下,自己能够带走宝箱的总价值最大是多少。
1 2 3 1 2
这题光看代码容易绕进去,先找个生活里的比方,比方对了,代码就是照着抄。
这道题出自 GESP 2024年6月,四级的编程基础题。它不难,但每年都有人在这里丢分,丢的地方还都一样。我们花十分钟把它从头捋一遍。
题目:宝箱
场次:2024年6月 四级|难度:四级
知识点:双指针
链接:https://www.acgo.cn/problemset/info/46127
小杨发现了 n 个宝箱,其中第 i 个宝箱的价值是 aᵢ。 小杨可以选择一些宝箱放入背包并带走,但是小杨的背包比较特殊,假设小杨选择的宝箱中最大价值为 x,最小价值为 y,小杨需要保证 x-y≤ k,否则小杨的背包会损坏。 小杨想知道背包不损坏的情况下,自己能够带走宝箱的总价值最大是多少。
一句话概括:用双指针把题目要求原样翻译成代码,属于考场上必须拿满分的题。
前提一,容器够不够大。题干没给明确范围,这类题的经验是:数据上千就用 long long,多占 4 个字节,换一个不出错。
前提二,两头有没有照顾到。最小规模先想一遍:n 等于 1 时程序会不会崩、答案是不是 0,这两种情况出题人最爱设陷阱。
前提三,交出去的样子对不对。第三件,最后注意输出格式。题目要几行就几行,行内空格几个就是几个,行末的换行别丢——算法对了格式错了,一样判错,这分丢得最冤。
先说这个比方。这题像照着说明书装家具:零件(输入)就那几样,说明书(题面)一步一步写清楚了,别自己加步骤。
- 排序:将所有宝箱按价值升序排列。 2. 遍历:对于每个宝箱
a[i],将其作为区间的右边界,向左扩展,计算所有符合条件的区间。 3. 计算总价值:对于每个合法的区间,计算该区间所有宝箱的总价值,并更新最大总价值。 4. 返回结果:最终输出最大总价值。
比方和代码是一一对应的:比方里先说清「有几样东西」,对应代码里的变量;比方里「一个一个过」,对应那个循环。
建议先自己写二十分钟,卡住了再看。对着抄一遍的效果,比不上自己错一遍。
using namespace std;
const int N = 1010;
int a[N];
int n, k;
int main() {
// 输入n和k
cin >> n >> k; // 读入
for (int i = 1; i <= n; i++) { // 遍历
cin >> a[i]; // 输入每个宝箱的价值
}
// 对宝箱的价值进行排序
sort(a + 1, a + n + 1);
int ans = 0; // 初始化答案
// 遍历每个宝箱作为区间的右边界
for (int i = 1; i <= n; i++) { // 遍历
int sum = 0; // 当前区间的总价值
// 从当前宝箱向左扩展
for (int j = i; j >= 1; j--) { // 遍历
if (a[i] - a[j] <= k) { // 如果满足条件
sum += a[j]; // 累加总价值
} else {
break; // 如果不满足条件,停止扩展
}
}
// 更新最大总价值
ans = max(ans, sum);
}
// 输出最大总价值
cout << ans << "\n"; // 输出
}
整份代码里真正需要想清楚的只有两处,我们只看这两处。
第一段,把数据读进来。
读入这段只要盯一件事:变量类型装不装得下。其他都可以照抄。
第二段,核心处理。
int sum = 0; // 当前区间的总价值
// 从当前宝箱向左扩展
for (int j = i; j >= 1; j--) {
if (a[i] - a[j] <= k) { // 如果满足条件
sum += a[j]; // 累加总价值
} else {
break; // 如果不满足条件,停止扩展
}
// …(这段后面还有,见上面的完整代码)
这段是整道题唯一需要想的地方,也是编程基础的落点。看循环时只问三句:从哪开始、到哪结束、每次加几。三句都对,这段就没错。
验证不是随便点几下提交,按下面的清单走一遍。
样例输入
1 2 3 1 2
样例输出
按这个顺序走一遍,跟上面那个比方对上:
- 跑题目给的样例,输出和样例逐字符一致,包括空格和换行。
- 把数据压到最少,边界情形下答案仍然对。
- 检查输出末尾,没有多余空格,最后一行有换行。
| 容易错的地方 | 错误写法 | 正确写法 |
|---|---|---|
| 排序方向写反 | sort(a, a+n) 想降序却用了默认升序 | 降序要写 sort(a, a+n, greater<int>()) |
| 递归层数爆栈 | 链状数据直接递归到 n 层 | 改显式栈,或把递归改成从底往上推 |
| 累加结果溢出 | int sum = 0; | 累加变量用 long long |
| 输出格式不符 | cout << ans; | cout << ans << "\n"; |
| 多组数据没清空 | 全局数组直接用 | 每组数据前 memset 或重新赋值 |
这题的经验压缩成三行,考前扫一眼就够。
- 这题考的:双指针——把题目条件一句一句翻译成代码,不添不减。
- 要记住的:题目给几行输入就按几行读,输出几个数就输出几个数,多一个空格都算错。
- 下一步:拿同场次另一道题练手,换题型不换节奏,手感就稳了。
系列按场次往前推,下一篇还在这个级别,难度会往上走一档。
- 本文属于《GESP 真题题解》系列,第 22 篇,真题按年份持续补齐,每篇都带完整可编译代码,题号可在 ACGO 直接提交验证。
- 还没动笔的话,先自己写一遍再回来看踩坑总结,比直接照抄代码收获大。
- 想跟完整系列的朋友点个关注,更新会第一时间推送。
- 本系列合集目录(按年份/组别排序)
GESP 的坑多半在边界和读题上。这道编程基础题把该注意的点都列在上面的表里了,提交前逐条过一遍。
今天想问你:如果把这题的数据范围扩大 10 倍,你的写法还撑得住吗?评论区聊聊你会怎么改。
把这篇转给一起刷题的同学,两个人对着讲一遍思路,比一个人看三遍都管用。关注本号不迷路。
后台回复 “资料”,领历年真题完整代码包(持续更新)。
本篇编号 GESP-064(公众号 MP-064)。完整目录与更多题解见博客专栏(公众号菜单「历史文章」)。