题解

56 条题解

  • 11
    @ 2017-05-07 12:51:58
    /*
    好题~ 学习了~
    一开始看到这题很容易想到那道经典的派(openjudge上有)
    那是一道典型的二分啊~
    这里也可以用到二分但是并不一样
    这里我们可以二分可以满足的人的数量
    首先我们要弄清这么一个事实
    如果是为了满足尽可能多的人
    我们满足嘴巴小的必然要比满足嘴巴大的好
    这个贪心决策很容易证明的
    如果同一块蛋糕一个嘴巴大的人能正好分到那一部分
    那么换一个嘴巴小的必然也能分到 还有可能因此多分到几个人
    所以我们可以发现先分嘴巴小的不会丢失最优解
    那么我们很容易就想到先按照嘴巴大小排个序
    那么我们二分这个满足人数mid后
    就要考虑是否能使mouth[1]~mouth[mid]都满足
    因为蛋糕的大小是不定的
    所以我们可以用dfs来完成
    即枚举每一个嘴巴是用哪一块来填饱
    首先我们记录下蛋糕总数sum 然后维护嘴巴大小的前序和数组s[]
    那么首先我们很容易想到
    对于排序后的mouth数组的前序和递增数组s[]
    如果总的sum比某个s[i]还要小
    那么根本没必要以i为二分右界
    因为不管怎么样是不可能满足的
    所以我们可以先缩小二分区域
    在搜索这里需要加上剪枝
    我们用waste来记录当前浪费的蛋糕数量
    怎么叫浪费呢  就是某一块切去这个人吃的之后连mouth[1]都满足不了了
    那么剩下的这些必然是浪费了
    这个只要在dfs时维护一个全局变量waste就可以了
    第二个剪枝
    如果对于排序后的mouth数组 dfs过程有mouth[k]==mouth[k-1]
    那么我们可以直接dfs(k-1,i)
    因为如果某个i不可以填满mouth[k]的话
    那么mouth[k-1]必然也填不满
    所以没有必要重新判断一次
    这样的话可以在12个点20ms的时间内出解
    还是挺快的
    关键是要学会一些常用的剪枝手段~
    涨姿势~!
    关于二分之后答案的输出
    窝太弱啦一向迷糊
    干脆直接加上一个ans来记录
    就万无一失啦~
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int MAXN=55;
    const int MAXM=1030;
    int s[MAXM];
    int cake[MAXN],fcake[MAXN];
    int mouth[MAXM];
    int n,m,sum;
    int waste,mid;
    int ans;
    
    void init()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&cake[i]);
            sum+=cake[i];
        }
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
            scanf("%d",&mouth[i]);
        sort(mouth+1,mouth+m+1);
        for(int i=1;i<=m;i++)
            s[i]=s[i-1]+mouth[i];
    }
    
    bool dfs(int k,int cur)//要满足k个人,当前到了cur
    {
        if(k<=0)
            return 1;
        if(sum-waste<s[mid])
            return 0;
        for(int i=cur;i<=n;i++)
            if(fcake[i]>=mouth[k])
            {
                fcake[i]-=mouth[k];
                if(fcake[i]<mouth[1])
                    waste+=fcake[i];
                if(mouth[k]==mouth[k-1])
                {
                    if(dfs(k-1,i))
                        return 1;
                }
                else    if(dfs(k-1,1))
                    return 1;
                if(fcake[i]<mouth[1])
                    waste-=fcake[i];
                fcake[i]+=mouth[k];
            }
        return 0;
    }
    
    int main()
    {
        init();
        while(sum<s[m])
            m--;
        int l=0,r=m;
        while(l<=r)
        {
            waste=0;
            for(int i=1;i<=n;i++)
                fcake[i]=cake[i];
            mid=(l+r)>>1;
            if(dfs(mid,1))
                l=mid+1,ans=max(ans,mid);
            else
                r=mid-1;
        }
        cout<<ans<<endl;
        return 0;
    }
         
    
  • 1
    @ 2018-11-25 16:58:50

    /*把人按口的大小排序,并记录前缀和与蛋糕总数,显然,前缀和是递增的,那么这样,我们可以通过缩小二分范围来达到加速的目的。若所有的蛋糕都不能满足某一个人的口,那么可以将其删去
    **
    waste浪费,对于一块蛋糕,将其分出去一部分满足一些人后,倘若剩余部分连口最小的人都无法满足,那么剩余部分一定不能满足任何人,就属于浪费的部分。若蛋糕有用的部分(总数-浪费)不能满足前mid个人,那么当前二分的答案不可行
    **
    由于口是递增的,在dfs过程中,可能会遇到这么一种情况,第i个人与第i-1个人的口相同,那么考虑,若不能满足第i-1个人,那么一定不能满足第i个人,进行剪枝
    */

    #include<stdio.h>
    #include<stdlib.h>
    #include<algorithm>
    #include<queue>
    using namespace std;
    int c[51],p[1100],n,m,b[51];
    priority_queue<int> tmp;
    bool cmp(int x,int y){
    return x>y;
    }
    bool check(int N){
    int i,j,time=1000;
    while(time--){//既然拼RP,当然要多rand几遍
    for(i=1;i<=n;i++)
    b[i]=c[i];//复制一份蛋糕副本
    random_shuffle(b+1,b+n+1);//该函数的功能是把一段区间随机打乱
    int flag;
    for(i=N;i>=1;i--){//这里对要满足的人从大到小枚举
    flag=0;
    for(j=1;j<=n;j++){//n比较小,暴力枚举蛋糕
    if(b[j]>=p[i]){
    flag=1;
    b[j]-=p[i];
    break;
    }
    }
    if(!flag) break;//如果找不到可以满足这个口的蛋糕,说明不行
    }
    if(flag) return true;
    }
    return false;
    }
    int main(){
    int i,j,l,r,mid,ans=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    scanf("%d",&c[i]);
    scanf("%d",&m);
    for(i=1;i<=m;i++)
    scanf("%d",&p[i]);
    sort(p+1,p+m+1);//贪心,口小的人优先取
    l=0;r=m;
    while(l<=r){//二分
    mid=l+r>>1;
    if(mid>=0&&check(mid)){
    ans=mid;
    l=mid+1;
    }
    else r=mid-1;
    }
    printf("%d",ans);
    return 0;
    }

  • 0
    @ 2012-07-29 20:35:45

    program ac;

     var tot,leave,i,j,n,m,k,l,r,mid,ans,st:longint;

         cake,mon,sum:array[0..1024] of longint;

         check:boolean;

    procedure swap(var x,y:longint);

     var t:longint;

    begin

         t:=x; x:=y; y:=t;

    end;

    procedure qsort(l,r:longint);

     var i,j,mid:longint;

    begin

         i:=l; j:=r; mid:=mon[(l+r) div 2];

         repeat

               while mon[i]

  • 0
    @ 2010-07-17 23:14:01

    #include

    #include

    #include

    #include

    #include

    #define MAXN 50

    #define MAXM 1024

    using namespace std;

    int cmp(const void *a , const void *b)

    {

    return ( *(int *)a - *(int *)b) ;

    }

    int pack[MAXN + 1] , rail[MAXM + 1] , N , M , total = 0 , sumr[MAXM + 1] , space , Mid , bag[MAXN + 1];

    bool Dfsid(int deep , int pos)

    {

    if (deep total - sumr[Mid]) return false ;

    for (int i = pos ; i = rail[deep])

    {

    bag[i] -= rail[deep] ;

    if (bag[i] < rail[1])

    space += bag[i] ;

    if (rail[deep] == rail[deep - 1])

    {

    if (Dfsid(deep - 1 , i)) return true ;

    }

    else

    if (Dfsid(deep - 1 , 1)) return true ;

    if (bag[i] < rail[1])

    space -= bag[i];

    bag[i] += rail[deep] ;

    }

    return false ;

    }

    int main()

    {

    //freopen("tmp.in","r",stdin);

    scanf("%d",&N);

    for (int i = 1 ; i 1 ) ;

    while (Left 1);

    }

    else

    {

    Right = Mid - 1 ;

    Mid = ((Left + Right) >> 1);

    }

    }

    printf("%d\n",Mid);

    return 0 ;

    }

  • 0
    @ 2010-04-13 21:23:06

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ├ 测试数据 11:答案正确... 0ms

    ├ 测试数据 12:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    改得不明不白就过了

  • 0
    @ 2010-03-18 21:05:36

    USACO的经典搜索题:

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ├ 测试数据 11:答案正确... 0ms

    ├ 测试数据 12:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-11-08 15:51:46

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ├ 测试数据 11:答案正确... 0ms

    ├ 测试数据 12:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-11-06 20:05:17

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ├ 测试数据 11:答案正确... 0ms

    ├ 测试数据 12:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    终于秒杀了

    2分写错了

    BJ

  • 0
    @ 2009-11-04 17:17:16

    太艰难了,提交11次,只因

  • 0
    @ 2009-10-03 20:08:27

    ...友情提示。。不能二分。。

    • @ 2016-11-15 10:21:45

      为什么不可以0.0

  • 0
    @ 2009-06-22 13:30:43

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ├ 测试数据 11:答案正确... 0ms

    ├ 测试数据 12:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    完美的秒杀,能减就减,注意DFS-ID最好用二分。

    附上源代码。

    program vijos;

    var i,j,m,n,min,l,r:integer;

    was,tot,x:longint;

    boo:boolean;

    cake:array[1..50] of longint;

    eat,need:array[0..1024] of longint;

    procedure sort(s,t:integer);

    var i,j:integer;

    x,z:longint;

    begin

    i:=s;

    j:=t;

    x:=need[(s+t) div 2];

    repeat

    while need[i]

  • 0
    @ 2009-05-21 13:02:52

    usaco上交过了

  • 0
    @ 2009-05-14 12:04:13

    加二分枚举答案得不到正确解,为什么?

    快排加上,最后一个点超时|无输出

    换成泡排,0ms

    why?????

  • 0
    @ 2009-03-26 17:52:39

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ├ 测试数据 11:答案正确... 0ms

    ├ 测试数据 12:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-03-23 20:32:51

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ├ 测试数据 11:答案正确... 0ms

    ├ 测试数据 12:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    AC!

  • 0
    @ 2009-03-14 19:38:35

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ├ 测试数据 11:答案正确... 0ms

    ├ 测试数据 12:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2008-12-05 21:06:47

    怎样剪啊

  • 0
    @ 2008-11-08 17:37:34

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ├ 测试数据 11:答案正确... 0ms

    ├ 测试数据 12:答案正确... 0ms

    二分+dfsid

    状态 dfs(r,s,t);

    r:蛋糕的搜索下界

    s:搜索到第几个人

    t:之前浪费的蛋糕量

    剪枝1:如果第s个人和第s-1个人想的相等,那么这两个人等效,那么我们假定s匹配的蛋糕在s-1的之前,即s-1 的r等于s-1匹配的蛋糕编号

    剪枝2:如果之前浪费的蛋糕量t+人的总需求>蛋糕总量,那么剪掉

  • 0
    @ 2008-10-26 18:27:18

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ├ 测试数据 11:答案正确... 0ms

    ├ 测试数据 12:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    艰难的AC历程!

    终于做到0ms过拉

    真的

    剪枝是很有技巧的哦

    就是下面的大牛所讲的那样就可以拉

信息

ID
1020
难度
7
分类
搜索 | 搜索与剪枝 点击显示
标签
(无)
递交数
2543
已通过
436
通过率
17%
被复制
10
上传者