2023-2024年USACO首次月考题目出炉！铜组第三题真题及解析

2023-2024赛季UASCO首场月赛已经圆满结束，晋级赛的最新试题也已经公布。没能当场晋级的同学们可以耐心等待一周，一周内USACO官方将会公布本次晋级赛成绩。如果没有晋级，12月可以当做一个练手+熟悉赛制的环节，1、2月的月赛持续发力，USACO可以重复挑战。

今天给大家分享铜级试题和解析，参赛的同学来看看解题思路，没参赛的同学来看看难度如何？

铜组第三题

INPUT FORMAT（标准输入）：

第一个将由一个整数T组成，表示独立测试用例的数量（1≤T≤10）。

每个测试用例的第一行由一个整数N组成。

第二行由N组成

整数hi（1≤hi≤109）

表示i的初始高度

第th株（英寸）。

第三行由N组成

整数ai（1≤ai≤109）

表示英寸数i每株植物每天都在生长。

第四行由N组成不同整数ti表示FJ给你的数组。保证N的总和

在所有测试用例中，不超过2·10^5。

输出格式（管道标准输出）：

输出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

样本输出：

0
3
2
5
-1
-1

在第一个样本输入中，有6个测试用例。

在第一个测试案例中，只有一个工厂，因此在第0天满足条件。

在第二个测试案例中，我们需要第一个植物比第二个植物短。第1天之后，高度分别为15和13。第二天之后，高度都是23。第3天之后，高度分别为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

且ai，hi≤103

输入6-8：N≤103

输入9-13：没有其他限制。

试题解析

考虑根据最终的排序结果来确定有多少条件，容易发现其实只有$n-1$个有效的不等式，即第1个小于第2个，第2个小于第3个，...

根据不等式origin_score[i]+increase[i]*t =origin_score[j]+increase[j]*t可以解出t对应的范围

最终对于所有不等式结果求出交集，如果不为空就输出最小值，否则输出-1

时间复杂度：O(n)

知识点：简单数学

核心代码如下：

USACO历年真题及参考书，扫码领取！【翰林提供报名指导服务】USACO历年真题及参考书

2023-2024年USACO活动时间

第一次月赛：2023年12月15日-18日

第二次月赛：2024年1月26日-29日

第三次月赛：2024年2月16日-19日

美国公开赛：2024年3月15日-18日

（中国学生只能参加到公开赛）

集训营：2024年5月23日-6月1日

EGOI：2024年7月21日-27日（荷兰）

IOI：2024年9月1日-8日（埃及）

报名方式：参赛者可随时在官网注册账号，注册。报名，只需在活动时间登陆完成答题即可。

官网地址：usaco.org

提交之后，官网会发送一份邮件到您邮箱，邮件中有账号密码

利用已知的账号于密码，登录USACO账号，即可开始考试