砍树 （二分）

看这里

Description

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

Input

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

Hint

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

思路

二分模拟
注意一点二分上界不能太大，否则会爆long long
给你个数据自己测测：

1 10000 1001 1000 1000

AC

#include<iostream> #include<algorithm> #include<stdio.h> #include<queue> #include<vector> #include<cmath> #define ll long long #define N 200005 using namespace std; int inf = 0x3f3f3f3f; double eps = 1e-5; ll h[N], a[N]; ll n, s, l; int check(ll day) {ll temp = 0;for (int i = 0; i < n; i++) {ll t = h[i] + day * a[i]; //要的是产量S，不需要把树折成 L，再进行统计 if (t >= l) temp += t; if (temp >= s) return 1; }return 0; } int main() { // freopen("in.txt", "r", stdin);while (scanf("%lld %lld %lld", &n, &s, &l) != EOF) {ll MAX = max(s, l), max_day = 1e18, min_day = 0;//min_day, max_day 分别表示二分的上下界 for (int i = 0; i < n; i++) {scanf("%lld", &h[i]);} for (int i = 0; i < n; i++) {scanf("%lld", &a[i]);ll days = (MAX - h[i]) / a[i] + 1;max_day = min(max_day, days); //为了防止check函数中爆long long，这里对右边界处理一下 }//二分枚举答案 while (min_day < max_day) {ll mid = (min_day + max_day) / 2;int status = check(mid);//如果 mid 合适就把右边界置为mid，否则左边界加 1 if (status) max_day = mid;else min_day = mid + 1;}ll ans = min_day;printf("%lld\n", ans); }return 0; }

总结

以上是生活随笔为你收集整理的砍树 （二分）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。