自动搬运

查看原文

来自洛谷，原作者为

	tder 喵喵喵。

搬运于2025-08-24 22:53:33，当前版本为作者最后更新于2023-12-24 20:36:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

伟大的不等式组。

---

令 $d_i(x)$ 表示第 $i$ 个植物经过 $t$ 天后的高度，有：

$$d_i(x)=h_i+t\times a_i$$

根据 $t$ 的定义，若用 $p_i$ 表示 FJ 希望长到第 $i$ 高的植物，易得，对于 $1\le x\le n$：

$$p_{t_x+1}=x$$

那么，若最少经过 $k$ 天后满足 FJ 的要求，显然有 $d_{p_1}(k)>d_{p_2}(k)>\cdots>d_{p_n}(k)$，即：

$$\begin{cases} d_{p_1}(k)>d_{p_2}(k) \\ d_{p_2}(k)>d_{p_3}(k) \\ \cdots \\ d_{p_{n-1}}(k)>d_{p_n}(k) \\ \end{cases} $$

分开来说，对于排名相邻的两个植物 $x=p_i$ 和 $y=p_{i+1}$，有 $d_{x}(k)>d_{y}(k)$，即 $h_x+k\times a_x>h_y+k\times a_y$，化简得：

$$(a_x-a_y)k>h_y-h_x$$

分类讨论 $a_x-a_y$ 的正负：

• 当 $a_x-a_y>0$，即 $a_x>a_y$ 时，有 $k>\frac{h_y-h_x}{a_x-a_y}$；
• 当 $a_x-a_y<0$，即 $a_x<a_y$ 时，有 $k<\frac{h_y-h_x}{a_x-a_y}$；
• 当 $a_x-a_y=0$，即 $a_x=a_y$ 时，有 $0>h_y-h_x$，即 $h_x>h_y$：
  • 若 $h_x>h_y$，$k\in\mathbb{R}$；
  • 反之，若 $h_x\le h_y$，无解。

此时我们得到了 $n-1$ 个不等式。其中，有 $l_1$ 个不等式 $k$ 大于某值，$l_2$ 个不等式 $k$ 小于某值，$l_3$ 个结果 $k\in\mathbb{R}$，以及 $l_4$ 个无解。

若 $l_4>0$，显然无解，输出 $-1$。由于 $k\in\mathbb{R}$，可以忽略所有 $l_3$ 个结果。接下来考虑剩余的 $l_1$ 个 $k>q1_i$ 和 $l_2$ 个 $k<q2_i$。那么，根据初中课本中的「同大取大，同小取小」，易得 $k>\max(q1_i)$ 及 $k<\min(q2_i)$。合并，得：

$$\max(q1_i)<k<\min(q2_i)$$

• 若 $\max(q1_i)<\min(q2_i)$，且区间 $(\max(q1_i),\min(q2_i))$ 中至少含有 $1$ 个正整数，则 $k=\lfloor\max(q1_i)\rfloor+1$；
• 反之，则无解。

时间复杂度 $O(T\cdot n)$。

---

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5, M = 1e9 + 5;
int T, n, h[N], a[N], t[N], p[N];
double q1 = -1, q2 = N;
int work() {
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>h[i];
    for(int i = 1; i <= n; i++) cin>>a[i];
    for(int i = 1; i <= n; i++) {
        cin>>t[i];
        p[t[i] + 1] = i;
    }
    if(n == 1) return 0;
    q1 = -1, q2 = M;
    for(int i = 1; i < n; i++) {
    	int x = p[i], y = p[i + 1];
		if(a[x] > a[y]) q1 = max(q1, 1.0 * (h[y] - h[x]) / (a[x] - a[y]));
		else if(a[x] < a[y]) q2 = min(q2, 1.0 * (h[y] - h[x]) / (a[x] - a[y]));
		else if(h[x] <= h[y]) return -1; 	
	}
    if(q1 < q2) {
		double r = floor(q1) + 1; 
		if(r < q2) return r;
		else return -1;
	} else return -1;
}
signed main() {
    cin>>T;
    while(T--) cout<<work()<<endl;
    return 0;
    // f(i) = h[x] + i * a[x], g(i) = h[y] + i * a[y]
	// f(i) > g(i)
	// h[x] + i * a[x] > h[y] + i * a[y]
	// (a[x] - a[y]) * i > (h[y] - h[x]) 
	// 1. a[x] - a[y] > 0, i > (h[y] - h[x]) / (a[x] - a[y])
	// 2. a[x] - a[y] < 0, i < (h[y] - h[x]) / (a[x] - a[y])
	// 3. a[x] - a[y] = 0, 0 > (h[y] - h[x])
	//   I.  h[y] - h[x] < 0, i in R
	//   II. h[y] - h[x] >= 0, i in empty
}