AcWing 4262. 空调
原题链接
简单
作者:
ofs
,
2024-04-11 23:42:13
,
所有人可见
,
阅读 2
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int b[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);
for (int i = 1; i <= n; i ++ )
{
int x;
scanf("%d", &x);
b[i] -= x; //求出来原数组与最后数组的差值
}
//构造差分数组
//注意此时差分数组要倒序构造
//如果正序构造,b[i] -= b[i - 1];b[i+1] -= b[i ];第一个式子中,b[i]已经被改变,导致第二个式子算出的b[i+1]错误
for (int i = n + 1; i; i -- ) b[i] -= b[i - 1];
//求所有正数的和,这个和就是最后的答案(需要自己证明)
int res = 0;
for (int i = 1; i <= n + 1; i ++ )//注意差分数组,右端点到n+1
if (b[i] > 0)
res += b[i];
printf("%d\n", res);
return 0;
}