题解

第一条题解
题目描述（水字数）
有 n 棵树，初始时每棵树的高度为 Hi​，第 i 棵树每月都会长高 Ai​。现在有个木料长度总量为 S 的订单，客户要求每块木料的长度不能小于 L，而且木料必须是整棵树（即不能为树的一部分）。现在问你最少需要等多少个月才能满足订单。

思路
在最坏的情况下，暴力的时间复杂度会达到O(Tn)(T为答案)，最大为20000×1e18，超出了计算机的运算速度。
答案具有单调性，所以，我们考虑二分。二分 需要的时间，然后进行检查，若mid不合法，l = mid + 1.若mid合法，先更新答案，再 r = mid - 1，最后输出答案

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
long long h[N],a[N],b[N];
int main()
{
    long long n,s,L;
    cin >> n >> s >> L;
    for(long long i = 1;i <= n;i++)
    {
        cin >> h[i];
    }
    for(long long i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    if(n == 1)//特判
    {
        cout << (s-h[1])/a[1];
    }
    long long ans = 1e18;
    long long l = 0,r = 1e18;
    while(l <= r)
    {
        long long mid = (l+r)/2;
        for(long long i = 1;i <= n;i++)
        {
            long long now = h[i] + 1LL * a[i] * mid;
            b[i] = now;
        }
        unsigned long long sum = 0;
        sort(b+1,b+n+1);
        for(int i = n;i >= 1;i--)//贪心,取最高的数
        {
            if(b[i] < L)
            {
                break;
            }
            sum += b[i];
            if(sum >= s)
            {
                break;
            }
        }
        if(sum >= s)//合法
        {
            ans=min(ans,mid);
            r = mid-1;
        }
        else l = mid + 1;
    }
    cout << ans;
    return 0;
}

附赠