海南省网站建设_网站建设公司_安全防护_seo优化

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;}