描述
Facer今天买了n块蛋糕，不料被信息组中球球等好吃懒做的家伙发现了，没办法，只好浪费一点来填他们的嘴巴。他答应给每个人留一口，然后量了量每个人口的大小。Facer有把刀，可以切蛋糕，但他不能把两块蛋糕拼起来，但是他又不会给任何人两块蛋糕。现在问你，facer怎样切蛋糕，才能满足最多的人。（facer的刀很强，切的时候不会浪费蛋糕）。
格式
输入格式
第一行n，facer有n个蛋糕。接下来n行，每行表示一个蛋糕的大小。再一行一个数m，为信息组的人数，然后m行，每行一个数，为一个人嘴的大小。(1<=n<=50, 1<=m<=1024)
输出格式
一行，facer最多可以填多少张嘴巴。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;
int waste,pre[
1100],tot=
0,n,m,cake[
60],mouth[
1100],left=
0,right,mid,last=
1314;
bool dfs(
int dep,
int pos){
if(dep>=mid&&pos<=n)
return 1;
if(tot-waste<pre[dep])
return 0;
for(
int i=pos;i<=n;i++){
if(cake[i]>=mouth[dep]){
cake[i]-=mouth[dep];
if(cake[i]<mouth[
1]) waste+=cake[i];
if(mouth[dep]==mouth[dep+
1])
if(dfs(dep+
1,pos))
return 1;
if(dfs(dep+
1,
1))
return 1;
if(cake[i]<mouth[
1]) waste-=cake[i];
cake[i]+=mouth[dep];
}
}
return 0;
}
int main(){
scanf(
"%d",&n);
for(
int i=
1;i<=n;i++) {
scanf(
"%d",&cake[i]);
tot+=cake[i];
}
scanf(
"%d",&m);
for(
int i=
1;i<=m;i++)
scanf(
"%d",&mouth[i]);
sort(mouth+
1,mouth+
1+m); pre[
0]=
0;
sort(cake+
1,cake+
1+n,greater<
int>());
for(
int i=
1;i<=m;i++) {
pre[i]=pre[i-
1]+mouth[i];
if(pre[i]<=tot) right=i;
}
for(mid=right;mid>=
0;mid--){
if(dfs(
1,
1))
break;
}
printf(
"%d",mid);
return 0;
}
转载于:https://www.cnblogs.com/leotan0321/p/6081380.html
