P9976 [USACO23DEC] Farmer John Actually Farms B 题解

tder · 2023-12-24 20:36:19 · 题解

伟大的不等式组。

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

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

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

分开来说，对于排名相邻的两个植物 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 的正负：

• 当 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)<\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
}