B3880 [信息与未来 2015] 买木头 题解

· · 题解

根据题目描述要求“最大长度”，我们可以知道这道题应该需要使用二分答案(看看数据范围，不然会超时)。

仔细理解题意，我们可以知道对于已经求出的木头最大长度length，可切割出的总木头数=每个商人的木头根数每个商人的单根木头所能切割出的最大数量，用表达式可表示为sum=sigma{si(li/length)}，用这个表达式可以判断对于二分出的每一个长度是否满足顾客需求量m，因为长度h需大于等于m。

现在我们来思考一下二分的范围，这个我使用闭区间[l,r]。l十分好想，就是可取的木头最小整数长度--1。而r就是所有商人的单根木头长度li中的最大值(不理解的话可以思考当每个商人有相同根木头，每根木头长度也相同的情况)。

接下来，我们只需要实现长度判断函数+二分答案，代码就出来了。代码如下：

#include <iostream>
using namespace std;
int n,m,l1,s1,maxl; //商人数量,需求量,第一个商人的木头单长度,第一个商人的木头数量,答案的最大取值
int a[10005],b[10005]; //单根长度,根数

//长度判断函数
bool cmp(int h){
    int s=0; //以h这个长度最多可以割的木头数量
    //对每个商人可割木头数量求和
    for (int i = 1;i <= n;i++) s += b[i]*(a[i]/h); //第i个商人可割总根数=根数*单根中可割根数
    if (s >= m) return 1; //以h这个长度最多可以割的木头数量大于需求量就满足条件
    else return 0;
}

int main(){
    cin >> n >> m >> l1 >> s1;
    a[1]=l1;b[1]=s1;
    maxl=a[1];
    //通过所给公式推导出每个商人的木头长度和数量
    for (int i = 2;i <= n;i++){
        a[i]=((a[i-1]*37011+10193)%10000)+1;
        b[i]=((b[i-1]*73011+24793)%100)+1;
        maxl=max(maxl,a[i]); //找最大长度的上边界
    }
    int l=1,r=maxl,mid; //[l,r]为满足要求的木头最大长度的取值范围(即最小长度为1,最大长度为maxl)
    //二分答案(找出木头最大长度)
    while (l <= r){
        mid=l+(r-l)/2;
        if (cmp(mid)) l=mid+1; //若以mid这个长度最多可以割的木头数量大于需求量,说明要求的可割木头的最大长度>=mid
        else r=mid-1; //否则说明比需求量小,应找更小的长度从而割更多的木头
    }
    cout << l-1; //结束时l=mid+1,mid为最大长度,则l-1即为所求
    return 0;
}