news 2026/11/5 18:07:01

2025年6月GESP真题及题解(C++七级): 调味平衡

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
2025年6月GESP真题及题解(C++七级): 调味平衡

2025年6月GESP真题及题解(C++七级): 调味平衡

题目描述

小 A 准备了n nn种食材用来制作料理，这些食材依次以1 , 2 , … , n 1,2,\dots,n1,2,…,n编号，第i ii种食材的酸度为a i a_iai​，甜度为b i b_ibi​。对于每种食材，小 A 可以选择将其放入料理，或者不放入料理。料理的酸度A AA为放入食材的酸度之和，甜度B BB为放入食材的甜度之和。如果料理的酸度和甜度相等，那么料理的调味是平衡的。

过于清淡的料理并不好吃，因此小 A 想在满足料理调味平衡的前提下，合理选择食材，最大化料理的酸度与甜度之和。你能帮他求出在调味平衡的前提下，料理酸度与甜度之和的最大值吗？

输入格式

第一行，一个正整数n nn，表示食材种类数量。

接下来n nn行，每行两个正整数a i , b i a_i,b_iai​,bi​，表示食材的酸度和甜度。

输出格式

输出共一行，一个整数，表示在调味平衡的前提下，料理酸度与甜度之和的最大值。

输入输出样例 1
输入 1
3 1 2 2 4 3 2
输出 1
8
输入输出样例 2
输入 2
5 1 1 2 3 6 1 8 2 5 7
输出 2
2
说明/提示

对于40 % 40\%40%的测试点，保证1 ≤ n ≤ 10 1 \le n \le 101≤n≤10，1 ≤ a i , b i ≤ 10 1 \le a_i,b_i \le 101≤ai​,bi​≤10。

对于另外20 % 20\%20%的测试点，保证1 ≤ n ≤ 50 1 \le n \le 501≤n≤50，1 ≤ a i , b i ≤ 10 1 \le a_i,b_i \le 101≤ai​,bi​≤10。

对于所有测试点，保证1 ≤ n ≤ 100 1 \le n \le 1001≤n≤100，1 ≤ a i , b i ≤ 500 1 \le a_i,b_i \le 5001≤ai​,bi​≤500。

核心思路

这道题可以转化为一个动态规划问题：我们需要选择若干食材，使得酸度之和与甜度之和相等（即差值之和为0），并最大化酸度与甜度之和（即所有选中的食材的a i + b i a_i+b_iai​+bi​之和）。

1.问题转换：
  • 每个食材有酸度a i a_iai​和甜度b i b_ibi​，定义差值d i = a i − b i d_i = a_i - b_idi​=ai​−bi​，价值v i = a i + b i v_i = a_i + b_ivi​=ai​+bi​。
  • 我们需要选择一个子集，使得 sum(d i d_idi​) = 0，并最大化sum(v i v_ivi​)。
2.动态规划设计：
  • 由于d i d_idi​可能为负，总差值范围在[-50000, 50000]之间（n ≤ 100,∣ d i ∣ |d_i|∣di​∣≤ 500），使用偏移量offset = 50000将负数下标转化为非负数。
  • 定义dp[j]表示当前考虑过的食材中，总差值（偏移后）为j时的最大总价值。
  • 初始状态：dp[offset] = 0，其余为负无穷。
  • 对于每个食材（d i d_idi​≠ 0）：
    • 若d i d_idi​> 0，则j从大到小更新，防止重复选择。
    • 若d i d_idi​< 0，则j从小到大更新，同样防止重复选择。
  • 对于d i d_idi​= 0的食材，直接将其价值累加到基础值中，因为选择它们不会影响差值，且总是优选的。
3.最终答案：
  • 最终dp[offset]即为满足平衡条件时的最大总价值。
4.复杂度分析
  • 时间复杂度：O(n × range)，其中 range = 100001，约为10 7 10^7107，在题目限制内可行。
  • 空间复杂度：O(range)，使用一维数组优化。

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintoffset=50000;// 差值偏移量，使负数下标可表示constintrange=100001;// 差值范围 [-50000, 50000] -> [0, 100000]constintINF=-1e9;// 负无穷，表示不可达状态intmain(){intn;cin>>n;intbase=0;// 基础价值：所有 d_i=0 的食材价值之和vector<pair<int,int>>items;// 存放 d_i ≠ 0 的食材 (d_i, v_i)for(inti=0;i<n;i++){inta,b;cin>>a>>b;intd=a-b;intv=a+b;if(d==0){base+=v;// d=0 的食材直接加入基础价值}else{items.push_back({d,v});}}// dp[j] 表示总差值（偏移后）为 j 时的最大总价值vector<int>dp(range,INF);dp[offset]=base;// 初始状态：不选任何非零食材，差值为0，价值为base// 动态规划处理每个非零食材for(auto&[d,v]:items){if(d>0){// 正差值：逆序遍历，避免重复选择for(intj=range-1;j>=0;j--){if(dp[j]!=INF&&j+d<range){dp[j+d]=max(dp[j+d],dp[j]+v);}}}else{// 负差值：正序遍历，避免重复选择for(intj=0;j<range;j++){if(dp[j]!=INF&&j+d>=0){dp[j+d]=max(dp[j+d],dp[j]+v);}}}}// 最终差值为0（即偏移后为offset）的最大价值即为答案cout<<dp[offset]<<endl;return0;}

功能分析

1.输入处理：
  • 读取食材数量n和每个食材的酸度、甜度。
  • 计算每个食材的差值d_i和价值v_i。
  • 将d_i = 0的食材价值累加到base中，其余存入items列表。
2.动态规划初始化：
  • dp数组初始化为负无穷，表示不可达状态。
  • dp[offset]初始化为base，代表不选任何非零食材时的基础状态。
3.状态转移：
  • 对每个非零食材，根据其差值正负决定遍历方向，确保每个食材只被考虑一次（0-1背包）。
  • 转移方程：dp[新差值] = max(dp[新差值], dp[原差值] +v i v_ivi​)。
4.输出结果：
  • 最终dp[offset]即为满足平衡条件的最大总价值。
5.示例验证
样例1
输入： 3 1 2 2 4 3 2 处理： 食材1: d=-1, v=3 食材2: d=-2, v=6 食材3: d=1, v=5 动态规划后，dp[offset]=8，输出8。
样例2
输入： 5 1 1 2 3 6 1 8 2 5 7 处理： 食材1: d=0, v=2 -> base=2 食材2: d=-1, v=5 食材3: d=5, v=7 食材4: d=6, v=10 食材5: d=-2, v=12 动态规划后，dp[offset]=2，输出2。

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转


GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/11/5 9:15:37

MoviePilot v2.3.6：影视管理效率革命性升级

MoviePilot v2.3.6&#xff1a;影视管理效率革命性升级 【免费下载链接】MoviePilot NAS媒体库自动化管理工具 项目地址: https://gitcode.com/gh_mirrors/mo/MoviePilot 你是否曾为繁琐的影视资源管理而烦恼&#xff1f;最新发布的MoviePilot v2.3.6版本将彻底改变你的…

作者头像 李华
网站建设 2026/11/5 2:05:59

3分钟破解：Beyond Compare永久授权密钥一键生成方案

3分钟破解&#xff1a;Beyond Compare永久授权密钥一键生成方案 【免费下载链接】BCompare_Keygen Keygen for BCompare 5 项目地址: https://gitcode.com/gh_mirrors/bc/BCompare_Keygen 还在为Beyond Compare的试用期限制而困扰吗&#xff1f;每次打开软件都面临评估错…

作者头像 李华
网站建设 2026/11/3 8:28:01

CosyVoice老年语音适配：3步云端调整语速语调

CosyVoice老年语音适配&#xff1a;3步云端调整语速语调 你是不是也遇到过这样的问题&#xff1f;自家开发的适老化软件&#xff0c;明明功能齐全、界面清晰&#xff0c;可老年人就是反馈“听不清”“太快了”“像机器人说话”。这背后其实不是产品做得不好&#xff0c;而是普…

作者头像 李华
网站建设 2026/11/2 20:12:57

RexUniNLU文本分类实战：云端10分钟出结果，3块钱玩一下午

RexUniNLU文本分类实战&#xff1a;云端10分钟出结果&#xff0c;3块钱玩一下午 你是不是也刷到过抖音上那些AI自动分析客户评论、给新闻分门别类的视频&#xff1f;看着特别高效&#xff0c;心里痒痒想试试&#xff0c;但一搜教程发现动不动就要RTX 4090显卡&#xff0c;朋友还…

作者头像 李华
网站建设 2026/11/4 11:44:02

释放创意：用ObjToSchematic将3D设计转化为Minecraft奇迹

释放创意&#xff1a;用ObjToSchematic将3D设计转化为Minecraft奇迹 【免费下载链接】ObjToSchematic A tool to convert 3D models into Minecraft formats such as .schematic, .litematic, .schem and .nbt 项目地址: https://gitcode.com/gh_mirrors/ob/ObjToSchematic …

作者头像 李华
网站建设 2026/11/4 11:31:50

Jellyfin元数据插件故障排查与架构优化实践

Jellyfin元数据插件故障排查与架构优化实践 【免费下载链接】jellyfin-plugin-metatube MetaTube Plugin for Jellyfin/Emby 项目地址: https://gitcode.com/gh_mirrors/je/jellyfin-plugin-metatube 当您的影视库中出现影片信息缺失、封面无法显示或演员资料空白时&…

作者头像 李华