Farmer John Actually Farms (USACO Bronze 2023 December)

我们需要找到一个最小的时间（天数），使得这个时间的时候，芦笋之间的高度满足FJ给的一系列要求，或者输出-1表示不可能。

容易看到，题目条件确定了芦笋的最终高度顺序，有 $t_i$ 株植物比 $i$ 高，意思就是 $i$ 是第 $t_i+1$ 名的意思，而 $t_i$ 又是互不相同的（distinct），所以这个顺序也是确定的。

直观的想法，每个pair的芦笋的关系，有一个对于时间的要求，这个要求是线性的，所以就是大于某一天，或者小于某一天，或者永远可以，或者永远不行四种可能性之一。我们把所有的两两芦笋之间的关系都跑一遍，得出的时间要求求交，就可以得到最小的全部满足的时间。这个方法无法得到满分，因为这是平方的复杂度。

这时我们观察到，因为最终的顺序是给定的，所以只需要相邻两个芦笋大小关系确定，整个的顺序也就确定了。所以我们只需要求解相邻植物带来的时间要求，再求交就可以了。

另外一个简单的优化，就是不用算两侧的范围，而是只算最小值，然后最后再验算一遍，看是否顺序正确，这样中间的过程更简单。

复杂度 $\mathcal{O}(N)$ 。

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int T;
int n;
ll h[200005], a[200005];
pi t[200005];       // pos,index
ll ans;
 
ll ceil_div(ll x, ll y) {
    return (x + y - 1) / y;
}
 
int main() {
    scanf("%d", &T);
    for (int test = 0; test < T; test++) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%lld", &h[i]);
        for (int i = 0; i < n; i++)
            scanf("%lld", &a[i]);
        for (int i = 0; i < n; i++) {
            scanf("%d", &t[i].first);
            t[i].second = i;
        }
        sort(t, t+n);
        ans = 0;
        for (int i = 0; i < n-1; i++) {
            // now height of t[i].second > t[i+1].second
            int p = t[i].second, q = t[i+1].second;
            if (h[p] > h[q])
                continue;
            if (a[p] > a[q])
                ans = max(ans, ceil_div(h[q]-h[p]+1, a[p]-a[q]));
            else {
                ans = -1;
                break;
            }
        }
        if (ans == -1) {
            printf("-1\n");
            continue;
        }
        for (int i = 0; i < n-1; i++) {
            // check it is actually in order
            int p = t[i].second, q = t[i+1].second;
            if (h[p]+ans*a[p] <= h[q]+ans*a[q]) {
                ans = -1;
                break;
            }
        }
        printf("%lld\n", ans);
    }
 
    return 0;
}