[bzoj5106][二分]汀博尔

80 阅读 0 评论 53 点赞

我是靠谱客的博主微笑龙猫，最近开发中收集的这篇文章主要介绍[bzoj5106][二分]汀博尔，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

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

Input

第一行3个用空格隔开的非负整数n,S,L，表示树的数量、订单总量和单块木料长度限制。
第二行n个用空格隔开的非负整数，依次为H1,H2,…,Hn。第三行n个用空格隔开的非负整数，依次为A1,A2,…,An。
1<=N<=200000,1<=S,L<=10^18,1<=Hi,Ai<=10^9

Output

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

Sample Input

3 74 51

2 5 2

2 7 9

Sample Output

7

【 Hints】

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

为 16, 54, 65，此时可以砍下第 2 和第 3 棵树完成订单了。

HINT

来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会荣誉出品。

Credit：idea/郑林楷　命题/郑林楷　验题/王聿中

Git Repo：https://git.thusaac.org/publish/CodePlus201711

本次比赛的官方网址：cp.thusaac.org

感谢腾讯公司对此次比赛的支持。

题解

可以发现一棵树要砍肯定最后那个月砍最优
那么二分答案，暴力check一下
二分上界不能无脑1e18会爆longlong，就设成一棵树能满足S时候的月份就好了
有个trick
对于L>S的情况，要设成一棵树满足L的月份。。
~~因为这个WA了半版~~

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
int n;LL S,L;
LL a[2100000],h[2100000];
bool check(LL p)
{
    LL ret=S;
    for(int i=1;i<=n;i++)
    {
        if(a[i]+h[i]*p>=L)ret-=a[i]+h[i]*p;
        if(ret<=0)return true;
    }
    if(ret<=0)return true;
    return false;
}
int main()
{
    scanf("%d%lld%lld",&n,&S,&L);
    LL maxx=0;
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&h[i]);
        maxx=max(maxx,(LL)(max(S,L)-a[i])/h[i]+100);
    }
    LL l=0,r=maxx,ans;
    while(l<=r)
    {
        LL mid=(l+r)/2;
        if(check(mid)){ans=mid;r=mid-1;}
        else l=mid+1;
    }
    printf("%lldn",ans);
    return 0;
}