[LOJ 6249]「CodePlus 2017 11 月赛」汀博尔

2022-05-15 12:46:08

Description

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

Input

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

Output

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

Sample Input

3 74 51
2 5 2
2 7 9

Sample Output

Hint

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

n <= 200000, S,L <= 1e18, a,h <= 1e9

来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会荣誉出品。
Credit：idea/郑林楷　命题/郑林楷　验题/王聿中
感谢腾讯公司对此次比赛的支持。

题解

比较裸的二分，主要是数据范围太恶心，容易爆$longlong$，调了好久...强行开$int128$才过。

 //It is made by Awson on 2017.11.27
 #include <map>
 #include <set>
 #include <cmath>
 #include <ctime>
 #include <queue>
 #include <stack>
 #include <cstdio>
 #include <string>
 #include <vector>
 #include <cstdlib>
 #include <cstring>
 #include <iostream>
 #include <algorithm>
 #define LL __int128
 #define Max(a, b) ((a) > (b) ? (a) : (b))
 #define Min(a, b) ((a) < (b) ? (a) : (b))
 using namespace std;
 ;

 int n;
 LL s, l, a[N+], h[N+];

 bool judge(LL mid) {
     LL cnt = ;
     ; i <= n; i++)
     if (mid >= (l-h[i])/a[i]+(bool)((l-h[i])%a[i])) {
         cnt += a[i]*mid+h[i];
         if (cnt >= s) return true;
     }
     return false;
 }
 void work() {
     scanf("%d%lld%lld", &n, &s, &l);
     ; i <= n; i++) scanf("%lld", &h[i]);
     ; i <= n; i++) scanf("%lld", &a[i]);
     LL L = , R = Max(l, s), ans;
     while (L <= R) {
     LL mid = (R+L)>>;
     ;
     ;
     }
     printf("%lld\n", ans);
 }
 int main() {
     work();
     ;
 }

码农公寓