猫史档案馆

#include<iostream>
#include<cstdio>
#include<stdio.h>
#include<algorithm>
#include<cmath>/*2分，搜索*/
using namespace std;
int n,m;
int tot=0;//用tot这个数组来记录这个数组的蛋糕总数 
int size_cake[55],num_peo[2000];
int sum[2025];//sum这个数组用来记前缀和 
int l,r;bool flag; 
int chi;
int ck;
//剪枝过程更多的是在dfs的判断中， 
void dfs(int x,int y)
{
    if(x<1)
    //分蛋糕的过程就像是乌鸦用石子，沙子，水去填满一个瓶子，聪明的乌鸦一定是先去用大的体积的东西去填，然后是小的
    //一旦是确定（假定） 了可以喂饱的人，就是要求到这往前从后往前喂同学们，如果分到了一个人，这个人的序号比1还要小，那么就是说明喂完了所有人
//返回true就ok  
    {
        flag=true;
        return;
    }
    for(int i=y;i<=n;i++)//是从第y块蛋糕开始分 
    {
        if(tot<chi)return;//如果我的 蛋糕的总数比人的需求总量还要少，那么不管我怎么去分蛋糕，我的结果都是false，这时候就没必要了直接返回
        if(flag)return;
        if(x<1)
        {
            flag=true;
            return;
         } 
         if(size_cake[i]>=num_peo[x])
         {
            size_cake[i]-=num_peo[x];
            tot-=num_peo[x];
            chi-=num_peo[x];
            if(tot<num_peo[1]&&x!=1)return;
            if(size_cake[i]<num_peo[1])tot-=size_cake[i];
            if(num_peo[x]==num_peo[x-1])dfs(x-1,i);
            else dfs(x-1,1);    
            if(size_cake[i]<num_peo[1])tot+=size_cake[i];
            size_cake[i]+=num_peo[x];
            tot+=num_peo[x];
            chi+=num_peo[x]; 
         }//因为这个过程不过只是自己假象的，所以就像是把皇后一样，一定要回溯，最后的时候蛋糕一点都会少，人们吃的蛋糕都会吐出来的 
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&size_cake[i]);
        tot+=size_cake[i];
    } 
    scanf("%d",&m);
    for(int j=1;j<=m;j++)scanf("%d",&num_peo[j]);
    sort(num_peo+1,num_peo+1+m);
    for(int i=1;i<=m;i++) sum[i]=sum[i-1]+num_peo[i];//前缀和是上一个人的前缀和+本人的嘴的大小 
    //先要进行第一个优化，如果给出一个前缀和，在二分答案之前首先要筛掉一些没有用的，就是如果前缀和大于tot，前缀和就要向前移动
    int oo=m;
    while(sum[oo]>tot)oo--;//通过前缀和饿进行优化 可以通过这一些剪枝来 减去没有必要的二分区间
    l=1,r=oo;
    while(l<=r)
    {
        int mid=(l+r)/2;
            flag=false;
        chi=sum[mid];
        dfs(mid,1);//mid是当前开始的人们所需要的蛋糕数目的总和，1是指从第一块蛋糕开始搜索
        //其实，蛋糕排序与否并不重要，都无所谓，不怕浪费时间去sort一行就自己写呗
        //dfs就是依据情况而定的check函数，不管怎么样，check函数都会返回一个值，根据这个值的情况进行下一步操作
        if(flag)//情况时可行的
        {
            l=mid+1;    
         } 
         else{
            r=mid-1;
         }

    }
    cout<<l-1<<endl;
}

问题 H: Facer切蛋糕 题目描述

　　Facer今天买了n块蛋糕，不料被信息组中球球等好吃懒做的家伙发现了，没办法，只好浪费一点来填他们的嘴巴。他答应给每个人留一口，然后量了量每个人口的大小。Facer有把刀，可以切蛋糕，但他不能把两块蛋糕拼起来，但是他又不会给任何人两块蛋糕。现在问你，facer怎样切蛋糕，才能满足最多的人。（facer的刀很强，切的时候不会浪费蛋糕）。

输入

第一行n，facer有n个蛋糕。接下来n行，每行表示一个蛋糕的大小。再一行一个数m，为信息组的人数，然后m行，每行一个数，为一个人嘴的大小。(1< =n< =50,  1< =m< =1024)

输出

一行，facer最多可以填多少张嘴巴。

样例输入 Copy

4
30
40
50
25
10
15
16
17
18
19
20
21
25
24
30

样例输出 Copy

7

给定m个人和n块蛋糕

首先是需要先sort一遍把人的嘴的大小拍一遍序，如果是我，的话，用有限的蛋糕，满足的更多的人，我会选择满足 嘴巴小的人 所以先sort一遍，把所有的人的嘴巴排序一遍，二分答案 WDC：二分的作用是先假定我可以满足x个人的嘴巴，每一次二分出一个答案后，都要对答案进行验证 而DFS、深搜的目的就是验证二分的区域对不对 根据二分答案的大，小来不断更新右边界，左边界直到找到一个确切的值

对于Dfs， operate：

1.先要维护一下目前的蛋糕的数量总共的大小 2.在维护目前的人的嘴的总需求， 3.维护一下每块蛋糕被啃后的大小

对于operate1 如果现在的蛋糕目前的数量不足以满足所有人的嘴的总数，直接return就ok，不可能满足了（这时候 flag是false，根据flag来调整可以满足的人的数量，那么调小区间就ok，）反之，如果flag是true的话，就说明 ，蛋糕数量 还不少啊，就可以调大了区间的大小， （operate1这一步主要是用来调一下去区间的大小）

对于operate2

时刻记录一下还需要的蛋糕数量 （与operate1结合分析），每次满足一个人，就把他的嘴删去

对于operate3

如果这个蛋糕被好多个人啃了，只剩下了一丢丢，那么如果这一丢丢的蛋糕渣渣就连第一个人都不能满足的话，那么 他就失去了存在的意义（有他没他都一样），那么operate1中维护的蛋糕剩余总数就要减去现在的蛋糕的大小 . . . . （优化） 剪枝，去掉一些显然没有用的步骤，起到优化的目的 省时间，空间

对于假定的人数，（就像是用石子，沙子，水填满水瓶一样，先填体积大的） dfs（x，j） 第x块蛋糕，第j个人， 对于x-1个人的嘴的大小一定是<=第x个人的嘴的大小

每一步都要判断一下当前的蛋糕数量和，人的需求的之间的比较

根据小于和等于进行剪枝， 如果是小于，就要从第一块蛋糕开始扫 for循环套起来（j 1---n） dfs(x-1,j)

如果x-1的嘴的大小和x的嘴的大小是一样的话 因为第x个嘴已经是从第1个扫到了第j个这时候发现第j个可以满足x的嘴 那么就说明第x-1张嘴（和第x张嘴是一样的，）就没有必要从第一个开始扫了 从第j个开始（第j个有可能还能满足x-1的嘴，如果j这块蛋糕足够大的话） . . . . 进行一系列操作 . . . . . . . . 回溯，怎么操作的怎么退回去（把蛋糕补回来，吃的蛋糕都吐出来） 这个深搜，是对假象的检验，也就是说，我的这个假象不一定是正确的，对于每一次假象，都要做好 假象是错误的回溯过程

深搜进行的每一步都是基于上一步是正确的这个条件下，从2号到5号，发现5号以后走不动了，那么就需要对从2--5的 操作进行复原，怎么来的怎么回去，在进行换一条路的搜索，直到结束，返回一定的值（flag） 他也会一直返回，进行完所有的搜索，（加入搜索成功了她会返回true然后，在返回，如果不成功，也会返回一定值 false然后在回溯，总之一定是会回溯的，只不过是时间不一样，从一条路换到另一条路是是在这一小步上直接回溯 搜到的最后，是全部从底部一步一步的向上回溯 ）

//剪枝过程更多的是在dfs的判断中， 
void dfs(int x,int y)
{
    if(x<1)
    //分蛋糕的过程就像是乌鸦用石子，沙子，水去填满一个瓶子，聪明的乌鸦一定是先去用大的体积的东西去填，然后是小的
    //一旦是确定（假定） 了可以喂饱的人，就是要求到这往前从后往前喂同学们，如果分到了一个人，这个人的序号比1还要小，那么就是说明喂完了所有人
//返回true就ok  
    {
        flag=true;
        return;
    }
    for(int i=y;i<=n;i++)//是从第y块蛋糕开始分 
    {
        if(tot<chi)return;//如果我的 蛋糕的总数比人的需求总量还要少，那么不管我怎么去分蛋糕，我的结果都是false，这时候就没必要了直接返回
        if(flag)return;
        if(x<1)
        {
            flag=true;
            return;
         } 
         if(size_cake[i]>=num_peo[x])
         {
            size_cake[i]-=num_peo[x];
            tot-=num_peo[x];
            chi-=num_peo[x];
            if(tot<num_peo[1]&&x!=1)return;
            if(size_cake[i]<num_peo[1])tot-=size_cake[i];
            if(num_peo[x]==num_peo[x-1])dfs(x-1,i);
            else dfs(x-1,1);    
            if(size_cake[i]<num_peo[1])tot+=size_cake[i];
            size_cake[i]+=num_peo[x];
            tot+=num_peo[x];
            chi+=num_peo[x]; 
         }//因为这个过程不过只是自己假象的，所以就像是把皇后一样，一定要回溯，最后的时候蛋糕一点都会少，人们吃的蛋糕都会吐出来的 
    }
}