算法题 翻转等价二叉树
2026/1/16 16:12:27
2024年12月GESP真题及题解(C++七级): 武器购买
题目描述
商店里有n nn个武器，第i ii个武器的强度为p i p_ipi，花费为c i c_ici。
小杨想要购买一些武器，满足这些武器的总强度不小于P PP，总花费不超过Q QQ，小杨想知道是否存在满足条件的购买方案，如果有，最少花费又是多少。
输入格式
第一行包含一个正整数t tt，代表测试数据组数。
对于每组测试数据，第一行包含三个正整数n , P , Q n,P,Qn,P,Q，含义如题面所示。
之后n nn行，每行包含两个正整数p i , c i p_i,c_ipi,ci，代表武器的强度和花费。
输出格式
对于每组测试数据，如果存在满足条件的购买方案，输出最少花费，否则输出-1。
输入输出样例 1
输入 1
3 3 2 3 1 2 1 2 2 3 3 3 4 1 2 1 2 2 3 3 1000 1000 1 2 1 2 2 3输出 1
3 -1 -1说明/提示
| 子任务编号 | 数据点占比 | n nn | p i p_ipi | c i c_ici | P PP | Q QQ |
|---|---|---|---|---|---|---|
| 1 11 | 20 % 20\%20% | ≤ 10 \leq 10≤10 | 1 11 | 1 11 | ≤ 10 \leq 10≤10 | ≤ 10 \leq 10≤10 |
| 2 22 | 20 % 20\%20% | ≤ 100 \leq 100≤100 | ≤ 5 × 10 4 \leq 5\times 10^4≤5×104 | 1 11 | ≤ 5 × 10 4 \leq 5\times 10^4≤5×104 | 2 22 |
| 3 33 | 60 % 60\%60% | ≤ 100 \leq 100≤100 | ≤ 5 × 10 4 \leq 5\times 10^4≤5×104 | ≤ 5 × 10 4 \leq 5\times 10^4≤5×104 | ≤ 5 × 10 4 \leq 5\times 10^4≤5×104 | ≤ 5 × 10 4 \leq 5\times 10^4≤5×104 |
对于全部数据，保证有1 ≤ t ≤ 10 1\leq t\leq 101≤t≤10，1 ≤ n ≤ 100 1\leq n\leq 1001≤n≤100，1 ≤ p i , c i , P , Q ≤ 5 × 10 4 1\leq p_i,c_i,P,Q\leq 5\times 10^41≤pi,ci,P,Q≤5×104。
思路分析
这是一个有总花费上限的01背包问题，但约束条件是总强度至少为P（而不是恰好等于）。我们需要在不超过总花费Q的前提下，选择武器使得总强度≥P，并求最小花费。
核心思路
这是一个二维约束的背包问题：
- 花费是成本，需要最小化
- 强度是收益，需要至少达到P
我们可以转换思路：用强度作为背包容量，求达到每个强度所需的最小花费，然后从强度≥P的方案中找出花费≤Q的最小值。
算法设计
使用动态规划：
- 状态定义：
dp[i]表示达到强度 i 所需的最小花费 - 初始状态：
dp[0] = 0，其他为无穷大 - 状态转移：对于每个武器(强度p，花费c)，从高到低更新：
dp[j] = min(dp[j], dp[max(0, j-p)] + c)
注意：当j-p < 0时，说明当前武器单独就能达到强度j，所以用max(0, j-p) - 最终答案：在
j ≥ P的所有状态中，找到dp[j] ≤ Q的最小dp[j]
时间复杂度
O(n × P)，其中n≤100，P≤50000，最坏情况5×10 6 10^6106次操作，可以接受。
代码实现
#include<bits/stdc++.h>usingnamespacestd;constintINF=1e9;// 无穷大值intmain(){ios::sync_with_stdio(false);cin.tie(0);intt;cin>>t;while(t--){intn,P,Q;cin>>n>>P>>Q;vector<int>p(n),c(n);for(inti=0;i<n;i++){cin>>p[i]>>c[i];}// dp[i]表示达到强度i所需的最小花费// 因为强度可能超过P，但最多不会超过P+最大单个强度intmaxSum=P+50000;// 最大可能强度vector<int>dp(maxSum+1,INF);dp[0]=0;// 强度为0时花费为0// 01背包：从高到低更新，保证每个武器只用一次for(inti=0;i<n;i++){intpi=p[i],ci=c[i];for(intj=maxSum;j>=0;j--){// 计算如果选择当前武器，能达到的强度intpre=max(0,j-pi);// 注意：强度不能为负if(dp[pre]!=INF){dp[j]=min(dp[j],dp[pre]+ci);}}}// 寻找答案：强度≥P且花费≤Q的最小花费intans=INF;for(inti=P;i<=maxSum;i++){if(dp[i]<=Q){ans=min(ans,dp[i]);}}if(ans==INF){cout<<"-1\n";}else{cout<<ans<<"\n";}}return0;}功能分析
1. 输入处理
- 读取测试用例数t
- 对于每个测试用例，读取n、P、Q和武器信息
- 使用vector存储武器数据
2. 动态规划核心
dp[i]存储达到强度i的最小花费- 初始化所有状态为无穷大，只有
dp[0]=0 - 遍历每个武器，从高到低更新dp数组
- 状态转移：
dp[j] = min(dp[j], dp[max(0, j-p)] + c)
3. 答案查找
- 遍历所有强度≥P的状态
- 找出其中花费≤Q的最小花费
- 如果找不到满足条件的解，输出-1
4.示例验证
对于第一个样例：
输入： 3 2 3 1 2 1 2 2 3 过程： dp[0]=0 武器1(1,2): dp[1]=2 武器2(1,2): dp[1]=min(2,0+2)=2, dp[2]=min(INF,0+2)=2 武器3(2,3): dp[2]=min(2,0+3)=2, dp[3]=min(INF,1+3)=4 强度≥2的最小花费：dp[2]=2≤3，输出2 但实际正确输出是3，为什么？ 问题分析： 我们需要总花费≤3，但dp[2]=2≤3是满足的。 但题目要求总花费不超过Q，且总强度≥P。 选择武器1和武器2：强度1+1=2≥2，花费2+2=4>3，不满足。 选择武器3：强度2≥2，花费3≤3，满足，所以最小花费是3。 我们的算法有问题吗？ 让我们重新检查算法： 武器1(1,2)：dp[1]=2 武器2(1,2)：更新时，从高到低： j=2: pre=max(0,2-1)=1, dp[2]=min(INF, dp[1]+2=4)=4 j=1: pre=max(0,1-1)=0, dp[1]=min(2, dp[0]+2=2)=2 武器3(2,3)：更新： j=3: pre=max(0,3-2)=1, dp[3]=min(INF, dp[1]+3=5)=5 j=2: pre=max(0,2-2)=0, dp[2]=min(4, dp[0]+3=3)=3 j=1: pre=max(0,1-2)=0, dp[1]=min(2, dp[0]+3=3)=2 最终dp[2]=3，强度≥2的最小花费是3，正确！5.复杂度分析
- 时间复杂度：O(t × n × (P + maxP))，最坏情况约10 × 100 × 100000 = 1e8次操作，可以接受
- 空间复杂度：O(P + maxP)，最大约100000
6.关键点总结
- 问题转化：将"至少达到P强度"转化为"达到强度i的最小花费"
- 边界处理：使用
max(0, j-p)处理j-p为负的情况 - 答案查找：在强度≥P的所有状态中找满足花费约束的最小值
- 优化剪枝：强度上限设为P+最大单个强度，避免不必要的计算
各种学习资料，助力大家一站式学习和提升！！！
#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;}