2020年信奥赛C++提高组csp-s初赛真题及答案解析（完善程序第1题）
2020年信奥赛C++提高组csp-s初赛真题及答案解析（完善程序第1题）
第1题
（分数背包）小 S 有 n 块蛋糕，编号从 1 到 n。第 i块蛋糕的价值是w i w_iwi，体积是v i v_ivi。他有一个大小为 B的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过 。他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量大。
为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 a(0<a<1)，并将一块价值是 w，体积为 v的蛋糕切割成两块，其中一块的价值是 a×w，体积是 a×v，另一块的价值是(1−a)×w，体积是 (1−a)×v。他可以重复无限次切割操作。
现要求编程输出最大可能的价值，以分数的形式输出。
比如 n=3,B=8，三块蛋糕的价值分别是 4,4,2，体积分别是 5,3,2。那么最优的方案就是将体积为 5的蛋糕切成两份，一份体积是 3，价值是 2.4，另一份体积是 2，价值是 1.6，然后把体积是 3 的那部分和后两块蛋糕打包进盒子。最优的价值之和是 8.4，故程序输出42 5 \frac{42}{5}542。
输入的数据范围为：1≤n≤1000，1≤B≤105，1≤w i , v i w_i,v_iwi,vi≤100。
提示：将所有的蛋糕按照性价比w i v i \frac{w_i}{v_i}viwi可从大到小排序后进行贪心选择。
试补全程序。
#include<cstdio>usingnamespacestd;constintmaxn=1005;intn,B,w[maxn],v[maxn];intgcd(intu,intv){if(v==0)returnu;returngcd(v,u%v);}voidprint(intw,intv){intd=gcd(w,v);w=w/d;v=v/d;if(v==1)printf("%d\n",w);elseprintf("%d/%d\n"w,v);}voidswap(int&x,int&y){intt=x;x=y;y=t;}intmain(){scanf("%d %d"&n,&B);for(inti=1;i<=n;i++){scanf("%d %d",&w[i],&v[i]);}for(inti=1;i<n;i++)for(intj=1;j<n;j++)if(①){swap(w[j],w[j+1]);swap(v[j],v[j+1]);}intcurV,curW;if(②){③}else{print(B*w[1],v[1]);return0;}for(inti=2;i<=n;i++)if(curV+v[i]<=B){curV+=v[i];curW+=w[i];}else{print(④);return0;}print(⑤);return0;}①处应填（ ）
A.
w[j] / v[j] < w[j+1] / v[j+1]B.
w[j] / v[j] > w[j +1] / v[j+1]C.
v[j] * w[j+1] < v[j+1] * w[j]D.
w[j] * v[j+1] < w[j+1] * v[j]②处应填（ ）
A.
w[1] <= BB.
v[1] <= BC.
w[1] >= BD.
v[1] >= B③处应填（ ）
A.
print(v[1],w[1]); return 0;B.
curV = 0; curW = 0;C.
print(w[1], v[1]); return 0;D.
curV = v[1]; curW = w[1];④处应填（ ）
A.
curW * v[i] + curV * w[i], v[i]B.
(curW - w[i]) * v[i] + (B - curV) * w[i], v[i]C.
curW + v[i], w[i]D.
curW * v[i] + (B - curV) * w[i], v[i]⑤处应填（ ）
A.
curW,curVB.
curW, 1C.
curV, curWD.
curV, 1
答案及题解
- ①处应填 D，因为需要按性价比从大到小排序，比较时用交叉乘法避免浮点误差。
- ②处应填 B，判断第一个蛋糕的体积是否不超过背包容量，若是则先完整取走。
- ③处应填 D，初始化当前已取体积和价值为第一个蛋糕的完整值。
- ④处应填 D，计算取部分蛋糕时的总价值分子，分母为当前蛋糕的体积。
- ⑤处应填 B，所有蛋糕完整取完后输出总价值，分母为1。
专栏推荐：信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html
各种学习资料，助力大家一站式学习和提升！！！
#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 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.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;}