admin 管理员组

文章数量: 1087649

二分——汀博尔

题目链接

二分——汀博尔

题目描述

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

输入描述

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

输出描述

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

示例

输入

3 74 51
2 5 2
2 7 9

输出

7

说明

对于样例，在六个月后，各棵树的高度分别为 14,47,56，此时无法完成订单。
在七个月后，各棵树的高度分别为 16,54,65，此时可以砍下第 2 和第 3 棵树完成订单了。

备注

1 ≤ n ≤ 200000，1 ≤ S,L ≤ 1018，1 ≤ Hi,Ai ≤ 109

分析

这题我们可以将需要等的月数进行二分查找，但需要注意一下二分边界。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
ll n,s,l,h[maxn],a[maxn],f[maxn],mx=-1;int check(ll mid)
{for(int i=0;i<n;i++){f[i]=h[i]+mid*a[i];		// mid 月后每棵树的高度 }ll sum=0; for(int i=0;i<n;i++){if(f[i]>=l){	// 当树的高度大于等于 l 时，更新 sum 值 sum+=f[i];}if(sum>=s){return 1;}}return 0;
}int main()
{cin>>n>>s>>l;for(int i=0;i<n;i++){cin>>h[i];}for(int i=0;i<n;i++){cin>>a[i];mx=max(mx,a[i]);}ll l=0,r=1e18/mx+1;	// 左右边界 while(l<=r){ll mid=(l+r)/2;if(check(mid)){r=mid-1;}else{l=mid+1;}}cout<<l<<endl;return 0;
}

本文标签： 二分汀博尔

版权声明：本文标题：二分——汀博尔 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1700299479a386205.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。