Logs

Problem Statement

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

Input

第一行 $3$ 个用空格隔开的非负整数 $n,S,L$，表示树的数量、订单总量和单块木料长度限制。

第二行 $n$ 个用空格隔开的非负整数，依次为 $H_1,H_2, … ,H_n$。

第三行 $n$ 个用空格隔开的非负整数，依次为 $A_1,A_2, … ,A_n$。

Output

输出一行一个整数表示答案。

Sample Input

Sample Output

1

7

Constraints

对于样例，在六个月后，各棵树的高度分别为 $14,47,56$，此时无法完成订单。

在七个月后，各棵树的高度分别为 $16,54,65$，此时可以砍下第 $2$ 和第 $3$ 棵树完成订单了。

Solving

我们容易注意到答案具有单调性，即月份越大，其树木的长度一定是越来越大的，我们只需要对于月份进行二分答案即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


const int N = 2e5+10;
const int M = 0;
int n,s,l;
int h[N],g[N];
bool check(int x)
{       
    int sum = 0;
    for(int i=1;i<=n;i++)
    {
        int val = h[i] + x * g[i];
        if(val>=l) sum += val;
        if(sum>=s) return true;
    }
    return false;
}
void solve()
{
    cin >> n >> s >> l;
    for(int i=1;i<=n;i++) cin >> h[i];
    for(int i=1;i<=n;i++) cin >> g[i];
    int l = 0,r = 1e18+1ull,mid;
    while(l+1!=r)
    {
        mid = (l+r) >> 1;
        if(check(mid)) r = mid;
        else l = mid;
    }
    if(!check(l)) l = r;
    cout << l;
}

注意：类似于while(l+1!=r)这类的二分答案写法，其并不会将答案直接明确地表明出在哪个边界，只是将答案范围缩小到了l和r其中的一个之间，我们需要根据题目的实际要求(max/min)，来多加一步判断。在本题中是if(!check(l))l=r;意为如果l不满足，则r就是需要的最小的月份。