A41794. 帮助
填空题
困难
知识点
题目描述
帮助
题目描述：
已知有M名需要帮助的贫困学生，及每名学生购买图书的金额；和N位愿意提供帮助的志愿者，及每名志愿者愿意帮助的金额。
现N名志愿者认领贫困生进行帮助，每人可以认领贫困学生的名额不限，但如果志愿者愿意帮助的金额小于每名贫困生购买图书的金额，那么该志愿者不能认领贫困学生。请你计算出这些志愿者最多可以认领多少名贫困学生（一名学生只能被一名志愿者认领）。
例如：M=5，N=2
5名贫困学生购买图书金额分别是：200、145、240、50、45，2名志愿者帮助金额分别为150、300。则最多可以认领4名学生。（金额300的志愿者认领200、50、45这3名学生，金额150的志愿者认领145这1名学生）
输入描述：
第一行输入一个正整数M（1<M<200），表示有M名贫困学生
第二行输入M个正整数（10<正整数<300），表示每名贫困生需要购买的图书金额，正整数之间一个空格隔开
第三行输入一个正整数N（1<N<50），表示有N名志愿者
第四行输入N个正整数（10<正整数<10000），表示N名志愿者帮助的金额，正整数之间一个空格隔开
输出描述：
输出一个整数，表示N名志愿者最多可以认领多少名贫困学生
样例输入：
5
200 145 240 50 45
2
150 300
样例输出：
4
参考答案
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int m,n,a[205],b[55],cnt;
void dfs(int p,int sum){
if(p>m) return;
for(int i=1;i<=n;i++){//被选走的情况
if(b[i]>=a[p]){
b[i]-=a[p];
cnt=max(cnt,sum+1);
dfs(p+1,sum+1);
b[i]+=a[p];
}
}
dfs(p+1,sum);//不选的情况
}
int main()
{
cin>>m;
for(int i=1;i<=m;i++) cin>>a[i];
cin>>n;
for(int i=1;i<=n;i++) cin>>b[i];
dfs(1,0);//从第1本书开始搜索，已赞助0人
cout<<cnt<<endl;
return 0;
}
上一题
下一题