AcWing 4262. 空调
原题链接
简单
作者:
无双飞怪
,
2024-04-17 16:31:03
,
所有人可见
,
阅读 1
思路:先让理想温度和现实温度做差 找到现实温度与理想温度的差值(记为差值数组)
由于每次发送的命令是让连续的区间+1或-1
在区间上动手脚(给这一段数+1或-1)我们想到了差分
所以在差值数组上差分 我们首先求出差值数组的差分情况
为了让所有牛都得到理想温度 那就是让差值数组全都变为0 => 也是让差分数组全都变为0(因为操作就是区间+1或-1)
而让差分数组全部变为0 差分数组中的每个数只要不为0 都可以通过差分操作(一个区间上+1或-1)让这个数变为0
而操作数就是所有的负值或正值(因为只要有一个数不为0就需要把他变为0 而每次操作只能变化1 所以操作数等于绝对值数)
而因为要想把一个区间的某个数变为0 那么根据差分操作:至少要两个数
因此要多出一个端点n+1来(把所有的最后一个1~n的端点之内的正数或负数的气都撒在n+1这个端点上 让最后一个1~n端点之内的数变为0)
故统计差分还是最后统计操作次数时都需要多统计一个n+1这个端点
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int b[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
a[i]-=b[i];
}
int res=0;
for(int i=n+1;i;i--) a[i]-=a[i-1];
for(int i=1;i<=n+1;i++) if(a[i]<0) res-=a[i];
cout<<res;
return 0;
}