AcWing 蓝桥杯集训·每日一题2025·5439. 农夫约翰真的种地

5439. 农夫约翰真的种地

题目描述

农夫约翰在他的农场种植了 $N$ 个芦笋，编号 $\sim N)$ 。
其中，第 $i$ 个芦笋的初始高度为 $h_i$ ，每经过一天高度会增长 $a_i$ 。
给定一个 $\sim N - 1)$ 的排列 $(t_1,t_2,\ldots,t_N)$ 。
请问至少多少天后能够满足，对于每个 $\leq i \leq N)$ ，恰好有 $t_i$ 个芦笋比第 $i$ 个芦笋的高度更高。

输入格式

第一行包含整数 (T)，表示共有 (T) 个测试数据。
每组数据：

第一行包含整数 $N$ 。
第二行包含 $N$ 个整数 $(h_1,h_2,\ldots,h_N)$ 。
第三行包含 $N$ 个整数 $a_1,a_2,\ldots,a_N$ 。
第四行包含 $N$ 个整数 $t_1,t_2,\ldots,t_N$ 。

输出格式

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

数据范围

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

解题思路

我们可以用一个结构体维护芦笋的最终高度排名（num），初始高度（st），每天增长高度（k）。
每个芦笋第 $(x)$ 天的高度对应一个式子 $(s t + k x)$ ，将芦笋按高度排名排序，对于任意两个相邻芦笋（st1在前），需解一个不等式 $(s t 1 + k 1 x > s t 2 + k 2 x)$ ，求出一个(x)的范围，所有(x)的范围取交集，无交集输出(-1)，有交集再输出(x)的最小值。

对于不等式 $(s t 1 + k 1 x > s t 2 + k 2 x)$ ，又可以分四种情况化简：
当 $\neq k2)$ 时，有两种情况：
$\begin{cases} x > \frac{st2 - st1}{k1 - k2} & (k1 - k2 > 0) \\ x < \frac{st2 - st1}{k1 - k2} & (k1 - k2 < 0) \end{cases} ]$
当 (k1 = k2) 时，只用看 (st1) 与 (st2)，如果 (st1 < st2)，则必定无解；如果 (st1 > st2)，则不等式恒成立。

所以主要处理当 $\neq k2)$ 时的两种情况，维护 (x) 的值域的上下限 $([min s, ma x s])$ 即可，对于 $(k 1 - k 2 > 0)$ 的，更新 $\max(mins, \frac{st2 - st1}{k1 - k2}))$ ，否则更新 $\min(maxs, \frac{st2 - st1}{k1 - k2}))$ 。

还要注意取整方向，可以在求下限时下向取整，更新时加上(1)；求上限时上向取整，更新时减(1)，这样就可以得到一个闭区间，详见注释。

AC Code

// Problem: 农夫约翰真的种地
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/5442/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
typedef long long ll; // 确保 ll 在使用前被定义
using namespace std;
using i64 = long long;
#define f for(int i = 0; i < n;++i)
#define ff for(int i = 1; i <= n;++i)
#define int long long 
#define pii pair<int,int>
#define In \ll n; \std::cin >> n;\

const int mod = 1e9 + 7, N = 1e7;struct Lus{int h; int a; int t;
};void solve(){In; std::vector<Lus> lus(n);f std::cin >> lus[i].h;f std::cin >> lus[i].a;f std::cin >> lus[i].t;if(n == 1) {std::cout << 0 << "\n";return ;}std::sort(lus.begin(), lus.end(), [&](const Lus a, const Lus b){return a.t < b.t;});// 排序 + 特判 // 对高度排序, 使用struct记录数据, // 判断当前有多少个满足条件的, 然后根据生长情况判断,// 天数累加情况下寻找满足条件的情况i64 ansL = 0, ansR = 1e9;for(int i = 0; i < n - 1; i ++) {i64 A = lus[i + 1].a - lus[i].a;i64 B = lus[i].h - lus[i + 1].h;if(A > 0) {ansR = std::min(ansR,(i64)ceil((double)B / A) - 1);} else if(A < 0) {ansL = max(ansL,(int)floor((double)B / A) + 1);} else if(B <= 0) {ansR = -1;}}if(ansL > ansR) ansL = -1;std::cout << ansL << "\n";
}signed main(){std::ios::sync_with_stdio(false);std::cin.tie(0); std::cout.tie(0);ll T = 1;std::cin >> T;for(int i = 1; i <= T; ++i) solve();
}