P10259: 种植计划
传统题
1.000s
时间限制
128MB
内存限制
16 提交
5 解决
【题目描述】
【题目描述】
农夫约(FJ)在他的农场上种植了N (1≤N≤2⋅10^5)株芦笋！但是一些植物有遗传差异，所以有些植物会比其他植物生长得更快。第i株植物的初始高度是hi英寸，每天过后，第ii株植物会生长ai英寸。
FJ会更偏爱某些植物，他希望某些特定的植物比其他植物要高。他给了你一个数组t1,…,tN，包含了从0到N−1的所有不同整数值，并且他希望对于第i株植物，有ti株植物的高度比它高。找出满足FJ要求的最少天数，或者确定这是不可能的。
【输入格式】
每个测试用例包含T个子测试用例。输入的第一行包含整数T(1≤T≤10)。以下是T个子测试用例。
每个子测试用例的第一行包含一个整数N。
第二行由N个整数hi(1≤hi≤10^9)组成，表示第i株芦笋的初始高度。
第二行由N个整数ai(1≤hi≤10^9)组成，表示每天第i株芦笋的生长高度。
第四行包括N个不同整数ti，这是FJ给你提供的数组。
保证所有测试用例中N的总和不超过2⋅10^5。
【输出格式】
输出T行，每行表示对应测试用例的答案。如果无法实现，则输出−1。
注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 "long long"）。
【样例输入】
6
1
10
1
0
2
７ ３
8 10
1 0
2
３ ６
10 8
0 1
2
７ ３
8 9
1 0
2
7 7
8 8
0 1
2
7 3
8 8
1 0
样例输出:
0
3
2
5
-1
-1
在第一个样例中，有6个测试用例。
在第一个测试用例中，只有一个植物，因此在第0天满足条件。
在第二个测试用例中，我们需要第一个植物比第二个植物短。第一天之后，高度是15和13。第二天之后，高度都是23。第三天之后，高度是31和33，这是第一天满足条件。
第三和第四个测试用例与第二个类似。
在第五个测试案例中，两株植物的初始高度为7，生长速率为8。所以它们总是有相同的高度，因此这个条件永远不满足。
在第六个测试用例中，初始条件不满足，增长率相同。所以这个条件永远不能满足。
样例输入:
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
样例输出:
4
7
在第二个示例输入中，有2个测试用例。
在第一个测试用例中，第4天之后的最终高度为19,20,21,18,16。
在第二个测试用例中，第7天之后的最终高度为25,17,19,35,36。
得分:
输入3:N≤2
输入4-5:N≤50
和人工智能,嗨≤103
输入6 ~ 8:N≤103
输入9-13:没有附加约束。
【输入】
第一行一个整数T，表示测试用例的个数(1≤T≤10)．
每个测试用例的第一行包含一个整数N．
第二行N个整数(1≤hi≤109)表示第i个植物的初始高度以英寸为单位。
第三行N个整数(1≤ai≤109)表示第i个植物每天生长的高度。
第四行N个整数ti表示FJ想要植物达到的高度。
可以保证N的和所有测试用例不超过2⋅105．
【输出】
输出T行，将每个测试用例的答案放在不同的行上。如果不可能，输出−1．
注意，这个问题中涉及的大尺寸整数可能需要使用64位整数数据类型(例如，C/ c++中的“long long”)。
【样例输入】复制
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