SCOI2005栅栏

2022-10-24 20:32:20

Description

　　农夫约翰打算建立一个栅栏将他的牧场给围起来，因此他需要一些特定规格的木材。于是农夫约翰到木材店购买木材。可是木材店老板说他这里只剩下少部分大规格的木板了。不过约翰可以购买这些木板，然后切割成他所需要的规格。而且约翰有一把神奇的锯子，用它来锯木板，不会产生任何损失，也就是说长度为10的木板可以切成长度为8和2的两个木板。你的任务：给你约翰所需要的木板的规格，还有木材店老板能够给出的木材的规格，求约翰最多能够得到多少他所需要的木板。

Input

　　第一行为整数m(m<= 50)表示木材店老板可以提供多少块木材给约翰。紧跟着m行为老板提供的每一块木板的长度。接下来一行(即第m+2行)为整数n(n <= 1000)，表示约翰需要多少木材。接下来n行表示他所需要的每一块木板的长度。木材的规格小于32767。（对于店老板提供的和约翰需要的每块木板，你只能使用一次）。

Output

　　只有一行，为约翰最多能够得到的符合条件的木板的个数。

Solution

先排序，二分能得到几块木板，然后搜索一下能不能切出这么多木块。详见代码。

思路借鉴了这位同学：http://www.cnblogs.com/2014nhc/p/6198644.html

Code

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 int a[],b[],c[];

 int n,m,tot,w,mid;

 bool check(int x)

 {

     bool fg;

     if (w>tot-c[mid]) return false;

     if (x==) return true;

     for (int i=; i<=m; i++)

     if (a[i]>=b[x])

     {

         a[i]-=b[x];//切掉这块

         if (a[i]<b[]) w+=a[i];//如果比最小的一块还要小，则算作废料

         fg=check(x-);

         if (a[i]<b[]) w-=a[i];//回溯

         a[i]+=b[x];

         if (fg) return true;

     }

     return false;

 }

 int main()

 {

     cin>>m;

     for (int i=; i<=m; i++)

     {

       cin>>a[i];

       tot+=a[i];

     }

     cin>>n;

     for (int i=; i<=n; i++)

       cin>>b[i];

     sort(a+,a+m+); sort(b+,b+n+);

     for (int i=; i<=n; i++)

       c[i]=c[i-]+b[i];

     while (c[n]>tot) n--;

     int left=,right=n,ans=;

     while (left<=right)

     {

         w=;

         mid=(left+right)/;

         if (check(mid)) {ans=mid; left=mid+;}

           else right=mid-;

     }

     cout<<ans<<endl;

     return ;

 }

Source

http://www.lydsy.com/JudgeOnline/problem.php?id=1082

码农公寓