AcWing 4262. 空调(详细注释版)
原题链接
简单
作者:
yimunai
,
2024-03-25 15:54:56
,
所有人可见
,
阅读 6
// 注意:变差分数组后因为差分有个操作涉及r + 1所以下标范围就从1到n变成了1到n+1
// 思路:首先肯定能想到要差分,可以先求出t和p之间的差距d数组,把问题转化成怎么从一个全0数组
// 变成这个d数组,难理解的点来了:可以求出d的差分数组b,然后看b中正数之和就是答案
// 可以这么理解:差分数组b只是d的另一种表达方式,例如将位置1到5温度加一表现在差分就是位置
// 1加一和6减一,所以差分数组中的一个正1就是一次操作,又因为差分中有一个加一就对应有
// 一个减一,所以答案是b中正数之和或负数之和的相反数
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int p[N], t[N];
int d[N], b[N];
void cal(int l, int r, int x)
{
b[l] += x;
b[r + 1] -= x;
}
int main()
{
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] = t[i] - p[i];
cal(i, i, d[i]);
}
int ans = 0;
for (int i = 1; i <= n + 1; i ++ ) // 注意下标
if (b[i] > 0)
ans += b[i];
cout << ans << endl;
return 0;
}