Drought

题意

有 N 头牛排成一行，第 i 头牛的饥饿度是 h[i]。

一次操作只能选择相邻的两头牛 i 和 i+1，让它们的饥饿度都减少 1，代价是 2 袋玉米。

要求用最少的玉米袋数，让所有牛最后的饥饿度相同，并且这个共同饥饿度不能为负数。如果做不到，输出 -1。

思路

先看一个小数据暴力。它枚举最后所有牛共同的饥饿度 f，然后从左到右模拟：如果当前位置比 f 大，就只能操作 (i, i+1) 把当前位置降到 f。

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/**
 * 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 17:58
 * update_at: 2026-07-11 18:02
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 25;
const ll INF = (1LL << 60);

int n;
ll h[MAXN], tmp_h[MAXN];

ll calc_cost(ll final_hunger) {
    for (int i = 1; i <= n; i++) {
        tmp_h[i] = h[i];
    }

    ll cost = 0;
    for (int i = 1; i <= n - 1; i++) {
        if (tmp_h[i] < final_hunger) {
            return INF;
        }

        ll need = tmp_h[i] - final_hunger;
        tmp_h[i] -= need;
        tmp_h[i + 1] -= need;
        cost += need * 2;
    }

    if (tmp_h[n] != final_hunger) {
        return INF;
    }
    return cost;
}

ll work_one_case() {
    cin >> n;

    ll min_h = INF;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
        if (h[i] < min_h) {
            min_h = h[i];
        }
    }

    ll ans = INF;
    // 枚举最终共同饥饿度，只适合小数据。
    for (ll final_hunger = 0; final_hunger <= min_h; final_hunger++) {
        ll cost = calc_cost(final_hunger);
        if (cost < ans) {
            ans = cost;
        }
    }

    if (ans == INF) {
        return -1;
    }
    return ans;
}

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

    int t;
    cin >> t;
    while (t--) {
        cout << work_one_case() << '\n';
    }

    return 0;
}

这个暴力的关键是：当我们已经处理完 1..i-1 后，位置 i-1 不能再被改变，所以要想让 h[i] 变成目标值 f，只能用 (i, i+1) 继续往右传递影响。

暴力需要枚举 f，如果 h[i] 很大就会太慢。满分做法不直接枚举 f，而是观察相邻两项的大小关系。

如果从左到右看到：

text

1h[i] > h[i-1]

那么为了让第 i 头牛不比第 i-1 头牛大，唯一能立刻起作用的操作是 (i, i+1)。所以必须做：

h[i] - h[i-1]

次操作，把 h[i] 降到 h[i-1]，同时 h[i+1] 也会被减少同样多。

第一遍从左到右处理完以后，如果最后还有 h[n] > h[n-1]，就没有位置可以继续帮 h[n] 降下去了，因此无解。否则整个序列会变成非递增。

接着把序列反转，再做同样的从左到右处理。反转后，相当于处理原来从右往左的限制。两遍结束后，如果所有数相等且不为负，就得到了最少代价；否则无解。

为什么这个贪心是最少的？因为每次遇到 h[i] > h[i-1] 时，至少要做 h[i]-h[i-1] 次操作 (i,i+1)，没有别的操作能在不影响已经处理好的左边位置的情况下修正 h[i]。所以这一步不是“可以这样做”，而是“必须这样做”。

代码

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/**
 * 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 17:58
 * update_at: 2026-07-11 18:02
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

int n;
ll h[MAXN]; // h[i] 表示第 i 头牛当前的饥饿度

ll work_one_case() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }

    if (n == 1) {
        return 0;
    }

    ll ans = 0;

    for (int round = 1; round <= 2; round++) {
        for (int i = 2; i <= n - 1; i++) {
            if (h[i] > h[i - 1]) {
                ll diff = h[i] - h[i - 1];
                // 只能通过操作 (i, i+1) 把 h[i] 降到 h[i-1]。
                h[i] -= diff;
                h[i + 1] -= diff;
                ans += diff * 2;
            }
        }

        if (h[n] > h[n - 1]) {
            return -1;
        }

        // 第一遍处理左边更小的情况，反转后再处理右边更小的情况。
        for (int l = 1, r = n; l < r; l++, r--) {
            swap(h[l], h[r]);
        }
    }

    for (int i = 2; i <= n; i++) {
        if (h[i] != h[1]) {
            return -1;
        }
    }

    if (h[1] < 0) {
        return -1;
    }
    return ans;
}

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

    int t;
    cin >> t;
    while (t--) {
        cout << work_one_case() << '\n';
    }

    return 0;
}

复杂度

每个测试用例只进行两次线性扫描和两次反转。

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

总结

本题的核心是把相邻操作看成“影响只能往未处理的一侧传递”。

左到右先修掉局部上升，反转后再修另一侧。每次修正的次数都是被迫的，因此总代价也就是最小代价。

目录

题意

思路

代码

复杂度

总结