2020年CSP-X复赛真题及题解（T3：侠盗阿飞）

2020年CSP-X复赛真题及题解T3侠盗阿飞题目描述侠盗阿飞获得了一笔意外之财w ww元钱他想用这笔钱去帮助需要帮助的人。现在知道有n nn个需要帮助的人以及他们每个人需要的钱数x i x_ixi​元i 0 , 1 , 2 , 3 , … , n − 1 i0,1,2,3,\dots,n-1i0,1,2,3,…,n−1阿飞应该如何支配这笔钱使得能得到帮助的人数最多输入格式第一行两个数阿飞的钱数w ww需要帮助的人数n nn。第二行n nn个数分别表示第i ii个人需要的钱数x i x_ixi​。输出格式只有一个整数表示阿飞最多能帮到的人数最多的人数。输入输出样例 1输入 110 5 1 2 3 4 5输出 14输入输出样例 2输入 21000 10 20 20 150 110 180 50 200 140 120 200输出 29说明/提示对于30 % 30\%30%的数据x i x_ixi​为升序序列x 0 x 1 x 2 x 3 … x_0\lt x_1\lt x_2\lt x_3\lt \dotsx0​x1​x2​x3​…。对于100 % 100\%100%的数据0 ≤ n ≤ 500 0\leq n\leq 5000≤n≤5000 x i ≤ 5 × 10 4 0 \lt x_i\leq 5\times 10^40xi​≤5×1040 ≤ w ≤ 2 × 10 9 0\leq w\leq 2\times 10^90≤w≤2×109。思路分析要帮助尽可能多的人应该优先帮助需要钱数最少的人。因此先对所有人的需求从小到大排序然后从最小的开始累加直到当前总花费加上下一个人的需求会超过总钱数w为止。这样得到的人数一定是最多的。代码实现#includebits/stdc.husingnamespacestd;intn,a[510];// n:人数, a:每个人需要的钱数longlongw;// 阿飞的总钱数intmain(){cinwn;for(inti0;in;i)cina[i];sort(a,an);//按需求从小到大排序longlongs0;//当前已经花费的钱数intc0;//最多能帮助的人数for(inti0;in;i){//从小到大尝试帮助每个人if(sa[i]w){//如果帮助这个人钱够sa[i];//累加花费c;//人数加一}elsebreak;//钱不够后面的需求更大直接结束}coutc;//输出答案return0;}功能分析使用贪心策略先帮助需求最小的人能够保证在有限的钱数下帮助到最多的人。对数组排序时间复杂度为O(n log n)n 500效率很高。使用long long存储钱数避免累加时溢出。当总花费加上当前人的需求超过w时因为数组已经升序后面的人需求更大所以直接结束循环。可以正确处理n 0或w 0的情况。更多内容请关注专栏信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}