Farmer John Actually Farms

题意

有 $N$ 株植物。第 $i$ 株植物初始高度为 $h_i$ ，每天长高 $a_i$ 。

给定一个排列 t，其中 t[i] 表示最终希望有恰好 t[i] 株植物比第 $i$ 株更高。

也就是说：

t[i] = 0 的植物最终必须最高。
t[i] = N-1 的植物最终必须最低。

求最少经过多少天后可以满足这个目标；如果永远不可能，输出 -1。

思路

先看一个小数据暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 16:21
 * update_at: 2026-07-11 16:23
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 55;
const int MAX_DAY = 1000;

int T;
int n;
long long h[MAXN];
long long a[MAXN];
int target_rank[MAXN];

bool check_days(long long days) {
    long long height[MAXN];
    for (int i = 1; i <= n; i++) {
        height[i] = h[i] + a[i] * days;
    }

    for (int i = 1; i <= n; i++) {
        int taller = 0;
        for (int j = 1; j <= n; j++) {
            if (height[j] > height[i]) {
                taller++;
            }
        }
        if (taller != target_rank[i]) {
            return false;
        }
    }

    return true;
}

int solve_one() {
    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 >> target_rank[i];
    }

    // 小数据暴力：直接枚举天数，找第一个满足目标排名的时刻。
    for (int days = 0; days <= MAX_DAY; days++) {
        if (check_days(days)) {
            return days;
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        cout << solve_one() << '\n';
    }

    return 0;
}

暴力直接枚举天数，算出当天所有植物高度，再统计每株植物有多少株比它高。这个做法能帮助我们确认题意，但满数据不能这样枚举。

把植物按目标排名排列：

text

1t = 0 的植物 > t = 1 的植物 > t = 2 的植物 > ...

如果所有相邻排名都满足严格变高关系，那么更远的关系会由传递性自动成立。所以只需要检查相邻排名：

text

1rank r 的植物高度 > rank r+1 的植物高度

设排名更高的植物为 big，排名更低的植物为 small。经过 x 天后需要：

h_{big} + a_{big}x > h_{small} + a_{small}x

如果一开始已经满足，就不需要因为这一对增加天数。

否则需要：

(a_{big} - a_{small})x > h_{small} - h_{big}

如果 $a_{big} \leqslant a_{small}$ ，这一对永远无法变成正确顺序，直接无解。

否则这一对给出一个最小天数下界：

x \geqslant \left\lceil \frac{h_{small}-h_{big}+1}{a_{big}-a_{small}} \right\rceil

对所有相邻排名取最大下界，得到候选答案 days。

最后必须再用 days 复查一遍所有相邻排名。原因是有些植物可能一开始顺序正确，但增长速度更慢；如果为了别的约束等了太久，它们可能又被反超。复查失败就输出 -1。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 16:21
 * update_at: 2026-07-11 16:23
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int T;
int n;
long long h[MAXN];
long long a[MAXN];
int target_rank[MAXN];
int pos_by_rank[MAXN]; // pos_by_rank[r] 表示目标排名为 r 的植物编号

long long ceil_div(long long x, long long y) {
    return (x + y - 1) / y;
}

bool check_days(long long days) {
    for (int r = 0; r + 1 < n; r++) {
        int big = pos_by_rank[r];
        int small = pos_by_rank[r + 1];

        long long big_height = h[big] + a[big] * days;
        long long small_height = h[small] + a[small] * days;
        if (big_height <= small_height) {
            return false;
        }
    }
    return true;
}

long long solve_one() {
    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 >> target_rank[i];
        pos_by_rank[target_rank[i]] = i;
    }

    long long days = 0;

    for (int r = 0; r + 1 < n; r++) {
        int big = pos_by_rank[r];
        int small = pos_by_rank[r + 1];

        if (h[big] > h[small]) continue;

        long long grow_diff = a[big] - a[small];
        if (grow_diff <= 0) {
            return -1;
        }

        long long need = h[small] - h[big] + 1;
        days = max(days, ceil_div(need, grow_diff));
    }

    if (!check_days(days)) {
        return -1;
    }

    return days;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        cout << solve_one() << '\n';
    }

    return 0;
}

复杂度

每个测试用例只扫描相邻排名常数次。

时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

总结

本题的关键是把 t[i] 理解成最终排名，并且只保留相邻排名的不等式。

先求所有相邻关系给出的最小等待天数，再复查这个天数是否真的让所有相邻关系成立。

Farmer John Actually Farms

目录

题意

思路

代码

复杂度

总结