切蛋糕
题目描述
Facer今天买了n块蛋糕，不料被信息组中球球等好吃懒做的家伙发现了，没办法，只好浪费一点来填他们的嘴巴。他答应给每个人留一口，然后量了量每个人口的大小。Facer有把刀，可以切蛋糕，但他不能把两块蛋糕拼起来，但是他又不会给任何人两块蛋糕。现在问你，facer怎样切蛋糕，才能满足最多的人。（facer的刀很强，切的时候不会浪费蛋糕）。
输入输出格式
输入格式：
第一行n，facer有n个蛋糕。接下来n行，每行表示一个蛋糕的大小。再一行一个数m，为信息组的人数，然后m行，每行一个数，为一个人嘴的大小。(1<=n<=50, 1<=m<=1024)
输出格式：
一行，facer最多可以填多少张嘴巴。
输入输出样例
输入样例#1：
4
30
40
50
25
10
15
16
17
18
19
20
21
25
24
30
输出样例#1：
7
分析：
一道极其恶心的搜索题。
首先我们不难想到，一块蛋糕可以给一个嘴大的人或者给几个嘴小的人，那显然是给嘴小的人能得到局部最优。但是局部最优并不一定能得到全局最优，所以我们要搜索啊（废话。。。先对所有人按嘴的大小排序，如果蛋糕总和也不能满足嘴最大的人，那么就可以直接把他踢出去了（23333,然后二分能满足的人数，深搜检验即可。
当然这样做复杂度肯定还是承受不了，还需要剪枝。因为有的蛋糕在给一些人吃了之后还有剩余，但是如果剩余部分连嘴最小的人也满足不了那就只能丢弃，我们就可以在dfs的时候记录一个waste值，表示不能在利用的蛋糕的大小，如果蛋糕总体积减去waste值小于剩余人数的需求值，就可以直接退出。加上这个优化以后复杂度就非常优秀了。
Code：
//It is made by HolseLee on 7th Aug 2018
//Luogu.org P1528
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std; const int N=;
const int M=;
int n,m,tot,waste,mou[M],all[M],c[N],t[N],ans,l,r,mid; inline int read()
{
char ch=getchar();int num=;bool flag=false;
while(ch<''||ch>''){if(ch=='-')flag=true;ch=getchar();}
while(ch>=''&&ch<=''){num=num*+ch-'';ch=getchar();}
return flag?-num:num;
} inline bool dfs(int num,int sta)
{
if(!num)return ;
if(tot-waste<all[mid])return ;
for(int i=sta;i<=n;++i)
if(t[i]>=mou[num]){
t[i]-=mou[num];
if(t[i]<mou[])waste+=t[i];
if(mou[num]==mou[num-]){
if(dfs(num-,i))return ;}
else {
if(dfs(num-,))return ;}
if(t[i]<mou[])waste-=t[i];
t[i]+=mou[num];
}
return ;
} int main()
{
n=read();
for(int i=;i<=n;++i){
c[i]=read();
tot+=c[i];
}
m=read();
for(int i=;i<=m;++i)mou[i]=read();
sort(mou+,mou+m+);
while(mou[m]>tot)m--;
for(int i=;i<=m;++i)
all[i]=all[i-]+mou[i];
l=,r=m;
while(l<=r){
waste=;
mid=(l+r)>>;
for(int i=;i<=n;++i)t[i]=c[i];
if(dfs(mid,))l=mid+,ans=mid;
else r=mid-;
}
printf("%d\n",ans);
return ;
}