Air Cownditioning

题意

有 N 个牛栏，第 i 个牛栏的目标温度是 p[i]，当前温度是 t[i]。

一次命令可以选择一个连续区间，让这个区间内所有温度同时升高 1 或降低 1。

要求最少需要多少条命令，才能让所有牛栏达到目标温度。

思路

先看一个小数据模拟。令：

d[i] = p[i] - t[i]

如果 d[i] > 0，说明第 i 个位置还需要升温；如果 d[i] < 0，说明还需要降温。暴力每次找一段连续同号的需求，把它们一起向 0 调整 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/**
 * 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 18:07
 * update_at: 2026-07-11 18:09
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n;
int p[MAXN], t[MAXN], d[MAXN];

int sign_of(int x) {
    if (x > 0) {
        return 1;
    }
    if (x < 0) {
        return -1;
    }
    return 0;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
    }
    for (int i = 1; i <= n; i++) {
        d[i] = p[i] - t[i];
    }

    int ans = 0;

    while (true) {
        int l = 1;
        while (l <= n && d[l] == 0) {
            l++;
        }
        if (l > n) {
            break;
        }

        int sgn = sign_of(d[l]);
        int r = l;
        while (r + 1 <= n && sign_of(d[r + 1]) == sgn) {
            r++;
        }

        // 对一段同号需求执行一次命令，让它们都向 0 靠近 1。
        for (int i = l; i <= r; i++) {
            d[i] -= sgn;
        }
        ans++;
    }

    cout << ans << '\n';

    return 0;
}

这个模拟能帮助理解操作本质：一次命令就是消掉某一层连续的同向需求。

满分做法可以直接数这些“层”的数量。

在 d 的两端各补一个 0：

text

1d[0] = 0, d[n+1] = 0

观察相邻位置的差：

text

1d[i+1] - d[i]

如果从 0 上升到 3，说明有 3 层区间在这里开始；如果从 3 下降到 1，说明有 2 层区间在这里结束。负数需求同理，只是方向相反。

因此所有层的开始和结束都会被相邻差统计到一次。每条实际命令有一个开始边界和一个结束边界，所以会被统计两次。

答案就是：

\frac{\sum_{i=0}^{n} |d[i+1] - d[i]|}{2}

这个公式同时处理升温和降温，因为取了绝对值。

代码

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

typedef long long ll;

const int MAXN = 100005;

int n;
ll p[MAXN], t[MAXN], d[MAXN];

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
    }

    d[0] = 0;
    d[n + 1] = 0;
    for (int i = 1; i <= n; i++) {
        d[i] = p[i] - t[i];
    }

    ll sum = 0;
    for (int i = 0; i <= n; i++) {
        sum += llabs(d[i + 1] - d[i]);
    }

    cout << sum / 2 << '\n';

    return 0;
}

复杂度

只需要读入数组并扫描一次差分变化。

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

总结

本题的关键是不要直接模拟每一条命令，而是把每个位置还差多少记成 d[i]。

连续区间操作在需求数组上对应一层连续区间。统计这些层的开始和结束，就得到相邻差绝对值之和的一半。

目录

题意

思路

代码

复杂度

总结