欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总贴：USACO历年青铜组真题解析 | 汇总-CSDN博客
【题目来源】
洛谷：[P9976 USACO23DEC] Farmer John Actually Farms B - 洛谷
【题目描述】
农夫约(FJ)在他的农场上种植了**N ( 1 ≤ N ≤ 2 ⋅ 10 5 ) N(1\le N\le 2\cdot 10^5)N(1≤N≤2⋅105)株芦笋！但是一些植物有遗传差异，所以有些植物会比其他植物生长得更快。第i株植物的初始高度是h i h_ihi英寸，每天过后，第i ii株植物会生长a i a_iai**英寸。
FJ会更偏爱某些植物，他希望某些特定的植物比其他植物要高。他给了你一个数组**t 1 , … t N t_1,\dots t_Nt1,…tN，包含了从0 00到N − 1 N-1N−1的所有不同整数值，并且他希望对于第i ii株植物，有t i t_iti**株植物的高度比它高。找出满足FJ要求的最少天数，或者确定这是不可能的。
【输入】
每个测试用例包含T TT个子测试用例。输入的第一行包含整数**T ( 1 ≤ T ≤ 10 ) T(1\le T\le 10)T(1≤T≤10)**。以下是T TT个子测试用例。
每个子测试用例的第一行包含一个整数N NN。
第二行由N NN个整数**h i ( 1 ≤ h i ≤ 10 9 ) h_i(1\le h_i\le 10^9)hi(1≤hi≤109)**组成，表示第i ii株芦笋的初始高度。
第二行由N NN个整数**a i ( 1 ≤ a i ≤ 10 9 ) a_i(1\le a_i\le 10^9)ai(1≤ai≤109)**组成，表示每天第i ii株芦笋的生长高度。
第四行包括N NN个不同整数**t i t_iti**，这是FJ给你提供的数组。
保证所有测试用例中N的总和不超过**2 ⋅ 10 5 2\cdot 10^52⋅105**。
【输出】
输出T TT行，每行表示对应测试用例的答案。如果无法实现，则输出− 1 -1−1。
注意这个问题涉及到的整数可能需要使用**64 6464**位整数型（例如，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【算法标签】
《洛谷 P9976 Farmer John Actually Farms》 #数学# #USACO# #O2优化# #2023#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;intT,n;structnode{longlongh,a,t;}p[200005];boolcmp(node x,node y){returnx.t<y.t;}intmain(){cin>>T;// 输入Twhile(T--){// 遍历T次询问cin>>n;// 输入nfor(inti=1;i<=n;i++)cin>>p[i].h;// 使用结构体数组，记录每个植物的h、a和tfor(inti=1;i<=n;i++)cin>>p[i].a;for(inti=1;i<=n;i++)cin>>p[i].t;if(n==1){// 如果n==1特判，输出0cout<<0<<endl;continue;}intminn=1e9,maxn=-1e9;// 定义满足条件的最大值和最小值sort(p+1,p+n+1,cmp);// 按照t从小到大方式排序intmark=0;// 定义标记位for(inti=1;i<n;i++){// 遍历n-1个植物inta=p[i].h,b=p[i].a,c=p[i+1].h,d=p[i+1].a;// 定义变量简化代码长度if(b==d){// 当b==d时if(a<=c){// 如果a小于等于c，永远无法追上，输出-1cout<<-1<<endl;mark=1;break;}else{// 否则，只需0天就可以满足maxn=max(maxn,0);}}if(b>d){// 当b>d时if(a<=c){// 如果a小于等于c，则在某天之后就一直超越intx=(c-a)/(b-d)+1;// 相减后相除的结果是相等的情况，还需要再加1maxn=max(maxn,x);}else{// 否则，只需0天就可以满足maxn=max(maxn,0);}}if(b<d){// 当b<d时if(a<=c){// 如果a小于等于c，永远无法追上，输出-1cout<<-1<<endl;mark=1;break;}else{intx=(a-c-1)/(d-b);// 否则开始超越，但到某天后就不再满足maxn=max(maxn,0);minn=min(minn,x);// 记录该minn}}}if(mark==1)continue;if(maxn>minn){// 要求maxn>minn，即满足条件maxn < x < minn，才有结果输出，否则输出-1cout<<-1<<endl;continue;}else{cout<<maxn<<endl;}}return0;}【运行结果】
6 1 10 1 0 0 2 7 3 8 10 1 0 3 2 3 6 10 8 0 1 2 2 7 3 8 9 1 0 5 2 7 7 8 8 0 1 -1 2 7 3 8 8 1 0 -1
