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

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

题目描述

侠盗阿飞获得了一笔意外之财w ww元钱，他想用这笔钱去帮助需要帮助的人。现在知道有n nn个需要帮助的人以及他们每个人需要的钱数x i x_ixi​元（i = 0 , 1 , 2 , 3 , … , n − 1 i=0,1,2,3,\dots,n-1i=0,1,2,3,…,n−1），阿飞应该如何支配这笔钱使得能得到帮助的人数最多？

输入格式

第一行：两个数，阿飞的钱数w ww，需要帮助的人数n nn。

第二行：n nn个数，分别表示第i ii个人需要的钱数x i x_ixi​。

输出格式

只有一个整数，表示阿飞最多能帮到的人数（最多的人数）。

输入输出样例 1

输入 1

10 5 1 2 3 4 5

输出 1

4

输入输出样例 2

输入 2

1000 10 20 20 150 110 180 50 200 140 120 200

输出 2

9

说明/提示

对于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≤500，0 < x i ≤ 5 × 10 4 0 \lt x_i\leq 5\times 10^40<xi​≤5×104，0 ≤ w ≤ 2 × 10 9 0\leq w\leq 2\times 10^90≤w≤2×109。

思路分析

要帮助尽可能多的人，应该优先帮助需要钱数最少的人。
因此先对所有人的需求从小到大排序，然后从最小的开始累加，直到当前总花费加上下一个人的需求会超过总钱数w为止。
这样得到的人数一定是最多的。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intn,a[510];// n:人数, a:每个人需要的钱数longlongw;// 阿飞的总钱数intmain(){cin>>w>>n;for(inti=0;i<n;i++)cin>>a[i];sort(a,a+n);//按需求从小到大排序longlongs=0;//当前已经花费的钱数intc=0;//最多能帮助的人数for(inti=0;i<n;i++){//从小到大尝试帮助每个人if(s+a[i]<=w){//如果帮助这个人钱够s+=a[i];//累加花费c++;//人数加一}elsebreak;//钱不够，后面的需求更大，直接结束}cout<<c;//输出答案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++标准模板库STL：
https://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 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}