AcWing 5439. 农夫约翰真的种地

题目描述

Week 2
2月27日

农夫约翰在他的农场种植了 $N$ 个芦笋，编号 $1\sim N$。

其中，第 $i$ 个芦笋的初始高度为 $h_i$，每经过一天高度会增长 $a_i$。

给定一个 $0\sim N-1$ 的排列 $t_1,t_2,\dots ,t_N$。

请问至少多少天后能够满足，对于每个 $1\le i\le N$，恰好有 $t_i$ 个芦笋比第 $i$ 个芦笋的高度更高。

输入格式

第一行包含整数 $T$，表示共有 $T$ 个测试数据。

每组数据第一行包含整数 $N$。

第二行包含 $N$ 个整数 $h_1,h_2,\dots ,h_N$。

第三行包含 $N$ 个整数 $a_1,a_2,\dots ,a_N$。

第四行包含 $N$ 个整数 $t_1,t_2,\dots ,t_N$。

输出格式

每组数据输出一行结果，一个整数表示答案，如果无解则输出 -1。

数据范围

$1\le T\le 10$, $1\le N\le 2\times 10^5$, $1\le h_i,a_i\le 10^9$, $0\le t_i\le N-1$, 保证 $t_1\sim t_N$ 是一个 $0\sim N-1$ 的排列, 一个测试点内所有的 $N$ 相加之和不超过 $2\times 10^5$。

输入样例1：

6  
1  
10  
1  
0  
2  
7 3  
8 10  
1 0  
2  
3 6  
10 8  
0 1  
2  
7 3  
8 9  
1 0  
2  
7 7  
8 8  
0 1  
2  
7 3  
8 8  
1 0

输出样例1：

0  
3  
2  
5  
-1  
-1

样例1解释

第 $1$ 组数据，由于只有一个芦笋，所以不需要经过任何天数，第 $0$ 天即可满足条件。

第 $2$ 组数据，我们需要使得第 $1$ 个芦笋比第 $2$ 个芦笋更矮：

天数 芦笋1 芦笋2
0 7 3
1 15 13
2 23 23
3 31 33

经过 $3$ 天后，即可满足条件。

第 $3,4$ 组数据与第 $2$ 组数据类似。

第 $5$ 组数据，两个芦笋的初始高度和生长速度都相同，所以永远保持相同高度，一定无法满足条件。

第 $6$ 组数据，两个芦笋的初始高度不满足条件，生长速度都相同，所以永远不可能满足条件。

输入样例2：

2  
5  
7 4 1 10 12  
3 4 5 2 1  
2 1 0 3 4  
5  
4 10 12 7 1  
3 1 1 4 5  
2 4 3 1 0

输出样例2：

4  
7

样例2解释

第 $1$ 组数据，$4$ 天后各个芦笋的最终高度为 $19,20,21,18,16$。

第 $2$ 组数据，$7$ 天后各个芦笋的最终高度为 $25,17,19,35,36$。

---

题意

给定 $n$ 个整数 $h_i$，每次操作会使 $h_i变为h_i+a_i$，求能否在若干次操作后使得 $h_i$ 的排名（从大到小）为 $t_i+1$。如果可以，求最小操作次数，否则输出-1。

r : rank
x: day

易得：

h[r[1]] + x * a[r[1]] > h[r[2]] + x * a[[2]] > ...... > h[r[n]] + x * a[r[n]]

根据不等式解得最小非负整数x

---

AC_code

python">import math  T = int(input())  
for _ in range(T):  n = int(input())  h = list(map(int, input().split()))  a = list(map(int, input().split()))  t = list(map(int, input().split()))  ans = 0  rank = [-1] * n  for i in range(n):  rank[t[i]] = i  l, r = 0, float('inf')  for i in range(n - 1):  A = h[rank[i]] - h[rank[i + 1]]  B = a[rank[i + 1]] - a[rank[i]]  if B > 0:  r = min(r, math.ceil(A / B) - 1)  elif B < 0:  l = max(l, math.floor(A / B) + 1)  elif A <= 0:  r = -1  break  if l > r:  ans = -1  else:  ans = l  print(ans)

---

END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢