acwing 4262 空调 | vegeone

vegeone
0%

acwing 4262 空调

发表于 分类于 Valine：

题意

几间房间有各自的温度，每次操作可以对连续的几间房间+1/-1度，请问使每个房间都到达目标温度的最小操作次数

思路

​ 将目标温度减去起始温度后会得到一串数列a，目标就是求使这串数列全部为0的操作次数，由于需要实现区间加，比较容易联想到使用差分来进行操作。

​ 转化为差分数组后，每次操作就可以转化为对于某个位置+1/-1，在对某个位置-1/+1，或者不存在后者（就是位置为数列尾部+1）。

​ 这样就只需要比较到底是+1的次数多还是-1的次数多即可

代码

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
const int N=1e5+10;
typedef pair<int,int>pp;
void solve()
{
    int n;
    cin>>n;
    vector<int>a(n+1),b(n+1),c(n+1),d(n+1);
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=n;++i)cin>>b[i];
    for(int i=1;i<=n;++i){
        c[i]=b[i]-a[i];
        // cerr<<c[i]<<" \n"[i==n];
    }
    for(int i=1;i<=n;++i){
        d[i]=c[i]-c[i-1];
        // cerr<<d[i]<<" \n"[i==n];
    }
    int ans1=0,ans2=0;
    for(int i=1;i<=n;++i){
        if(d[i]<0)ans1+=abs(d[i]);
        else ans2+=d[i];
    }
    cout<<max(ans1,ans2)<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    // cin>>T;
    while(T--)	solve();
    return 0;
}