Code Plus

Description

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

Solution

二分多少个月能满足订单.

因为sb的二分范围整整交了23遍, 还换了种语言写.

Codeo

C++

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
31
32
33
34
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int N = 200005;
long long h[N], A[N];
bool Judge(long long mid, long long L, long long S, int n) {
unsigned long long siz = 0;
for (int i = 1; i <= n; i += 1)
if ((unsigned long long) (h[i] + A[i] * mid) >= L)
if ((siz += h[i] + A[i] * mid) >= S)
return true;
return false;
}
int main () {
int n;
long long S, L;
scanf("%d%lld%lld", &n, &S, &L);
for (int i = 1; i <= n; i += 1)
scanf("%lld", &h[i]);
for (int i = 1; i <= n; i += 1)
scanf("%lld", &A[i]);
long long l = 0, r = 1e18, mid;
while (l <= r) {
mid = l + r >> 1;
if (Judge(mid, L, S, n)) r = mid - 1;
else l = mid + 1;
}
printf("%lld\n", l);
return 0;
}

Python

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
31
32
33
34
h = []
A = []
def judge(mid, n, S, L):
now = 0
for i in range(n):
if h[i] + A[i] * mid >= L:
now += h[i] + A[i] * mid
if now >= S:
return True
return False
tmp = input()
tmp = list(map(int, tmp.split(' ')))
n = tmp[0]
S = tmp[1]
L = tmp[2]
tmp = input()
h = list(map(int, tmp.split(' ')))
tmp = input()
A = list(map(int, tmp.split(' ')))
l = 0
r = 0
for i in range(n):
r = max(r, (L - h[i] + 1000000000) // A[i] + 1)
while l <= r:
mid = l + r >> 1
if judge(mid, n, S, L) == True:
r = mid - 1
else :
l = mid + 1
print(l)
-------------本文结束感谢您的阅读-------------