【洛谷 1528】切蛋糕

题目描述

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

题解：好熟悉的题目emmm，直接上代码吧，小小的剪枝，大大的作用。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1050;
int a[N],b[N],c[N],n,mid,m,w,tot,sum[N],ans;

bool check(int h,int last){
    bool ff=false;
    if(tot-w<sum[mid]) return 0;//剪枝,如果总数减去浪费数<1~mid需要总数,就肯定不行了。 
    if(h==1) return 1;
    for(int i=last;i<=m;i++){
        if(a[i]-b[h]>=0){
            a[i]-=b[h];
            if(a[i]<b[1]) w+=a[i];

            if (b[h]==b[h-1]) ff=check(h-1,i);
            else ff=check(h-1,1);

            if(a[i]<b[1]) w-=a[i];
            a[i]+=b[h];

            if(ff==true) return 1;//如果之后的尝试中返回可行，那就返回true
        }
    }
    return 0;
}

int main(){
    freopen("1528.in","r",stdin);
    freopen("1528.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        tot+=a[i]; c[i]=a[i];
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&b[i]);
    }
    sort(b+1,b+m+1);
    for(int i=1;i<=m;i++)
        sum[i]=sum[i-1]+b[i];
    while(sum[m]>tot) m--;
    int l=1,r=m;
    while(l<=r){
        w=0; mid=(l+r)/2;
        for(int i=1;i<=n;i++) a[i]=c[i];
        if(check(mid,1)==1) { ans=mid; l=mid+1; }
        else r=mid-1;
    }
    if(l==2) printf("0\n");
    else printf("%d\n",l-1);

    return 0;
}