【bzoj1082】 SCOI2005—栅栏

http://www.lydsy.com/JudgeOnline/problem.php?id=1082 (题目链接)

题意

　　给出m块木柴，以及n块木板，要求将m块木柴做木板，要求将木柴切割成与木板一样的长度，问最多可以做成几块木板。

Solution

　　今日考题。乍一看，好像可以二分，然而并不会check，于是码了个贪心，10分mdzz。。

　　正解：二分+搜索。

　　每次二分答案mid后，对每块木板进行搜索，枚举用那根木柴去进行切割。没想到剪枝这么强大，这都可以搜过去。。

　　剪枝1：一开始将不符合条件的某些木柴与木板去掉。

　　剪枝2：有些木柴经过切割后已经比最短的木板更短，将剩下的长度加到一个变量Waste中，判断是否  Waste + mid块木板总长度>木柴总长度。

　　剪枝3：若某块木板在之前已经搜索过了，直接从当时被切割的木柴处进行搜索。

代码

// bzoj1082

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<queue>

#define LL long long

#define inf 2147483640

#define MOD 1000000009

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=10010;

int a[maxn],b[maxn],S,sum[maxn],bl[maxn];

int n,m,flag,mid;

void dfs(int x,int p,int w) {

    if (x==0) {flag=1;return;}

    while (p<=n && a[p]<b[1]) {w+=a[p];p++;}

    if (w+sum[mid]>S || flag || p>n) return;

    int t=p;

    if (b[x]==b[x+1] && x!=mid) t=bl[x+1];

    for (int i=t;i<=n;i++) if (a[i]>=b[x]) {

            bl[x]=i;

            a[i]-=b[x];dfs(x-1,p,w);

            a[i]+=b[x];

            if (flag) return;

        }

}

int main() {

    scanf("%d",&n);

    for (int i=1;i<=n;i++) scanf("%d",&a[i]);

    scanf("%d",&m);

    for (int i=1;i<=m;i++) scanf("%d",&b[i]);

    sort(a+1,a+1+n);

    sort(b+1,b+1+m);

    while (b[m]>a[n]) m--;

    int tot=0;

    for (int i=1;i<=n;i++) if (a[i]>b[1]) a[++tot]=a[i];

    n=tot;S=0;sum[0]=0;

    for (int i=1;i<=n;i++) S+=a[i];

    for (int i=1;i<=m;i++) sum[i]=sum[i-1]+b[i];

    int L=1,R=m,ans=0;

    while (L<=R) {

        mid=(L+R)>>1;

        flag=0;dfs(mid,1,0);

        if (flag) ans=mid,L=mid+1;

        else R=mid-1;

    }

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

    return 0;

}