题解 - Vijos

11

/*
好题~ 学习了~
一开始看到这题很容易想到那道经典的派(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

风腾 LV 8 @ 6 年前

/*把人按口的大小排序，并记录前缀和与蛋糕总数，显然，前缀和是递增的，那么这样，我们可以通过缩小二分范围来达到加速的目的。若所有的蛋糕都不能满足某一个人的口，那么可以将其删去
**
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

csw LV 8 @ 12 年前

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

搁浅 LV 9 @ 14 年前

#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

prince_hao LV 10 @ 14 年前

编译通过...

├ 测试数据 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

qiaomingda LV 8 @ 15 年前

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

hds108 LV 8 @ 15 年前

编译通过...

├ 测试数据 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

yzl609271536 LV 10 @ 15 年前

编译通过...

├ 测试数据 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

superyoi LV 7 @ 15 年前

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

0

zxytim LV 10 @ 15 年前

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

DaisyGao @ 8 年前

为什么不可以0.0

0

怪盗~基德 LV 10 @ 15 年前

编译通过...

├ 测试数据 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

zhujf553 LV 10 @ 15 年前

usaco上交过了

0

hitman47 LV 8 @ 15 年前

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

快排加上，最后一个点超时｜无输出

换成泡排，0ms

why?????

0

zhjifa LV 7 @ 16 年前

编译通过...

├ 测试数据 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

chengrui LV 10 @ 16 年前

编译通过...

├ 测试数据 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

boyzkk LV 10 @ 16 年前

编译通过...

├ 测试数据 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

FenXy LV 10 @ 16 年前

http://www.nocow.cn/index.php/USACO/fence8

puppy0ms

0

305636397 LV 6 @ 16 年前

怎样剪啊

0

razhangwei LV 3 @ 16 年前

编译通过...

├ 测试数据 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

king13 LV 8 @ 16 年前

编译通过...

├ 测试数据 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过拉

真的

剪枝是很有技巧的哦

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

题解

56 条题解

切蛋糕

信息

状态

开发

支持

题解

56 条题解

切蛋糕

信息

状态

开发

支持

还没有账户？

登录