题目描述
解题思路:step1:求出目标温度p[N]和现有温度t[N]的差值
(即要改变温度的数组,将其定义为数组 b[N])
step2:正常想法,构造一个全0的差分数组s[N],如果
能够将差分数组s[N]变成b[N]数组,在将变后的
差分数组s[N]加上t[N]就可以得到p[n],所以题
目中所要求的就是将s[N]变成b[N]需要操作几步。
step3:若需要将s[N]变为b[N],需要知道l,r,c(操作数)三个值,
但现在这三个值都没有。因此想到将b[N]变为全 0 的s[N]所需
要的步骤等于将s[N]变为b[N]。
step4:将s[N]变为b[N]需要两步操作
1.改变两个位置上的值(设为bl[N])
2.求前缀和
那么反过来b[N]变为s[N]也需要两个步骤
1.前缀和的逆运算b[i]-=b[i-1]得到了bl[N]
2.在本题中根据bl[N]求出步骤即可
step5:根据bl[N]求出需要几步
首先明确在本题中只有两种操作 1.s[l]+=/-=1,s[r+1]-=/+=1(对两个位置分别进行操作)
2.只选中一个位置进行+1/-1.
所以根据这两种操作方式 当pos(bl[N]中正数和)=neg(bl[N]中负数和)也就是说只执行第一种操作执行 pos(neg)次
当pos>neg/neg>pos时需要执行这两种操作max(pos,neg)次
样例
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010;
int n;
int p[N],t[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&p[i]);
}
for(int i=1;i<=n;i++){
scanf("%d",&t[i]);
p[i]-=t[i];
}//求出每一项需要改变的数值存放在了p中
for(int i=n;i>1;i--) p[i]-=p[i-1];//step4中前缀和的逆运算
int pos=0,neg=0;
for(int i=1;i<=n;i++){
if(p[i]>0) pos+=p[i];
else neg-=p[i];
}
if(pos>=neg) cout<<pos<<endl;
else cout<<neg<<endl;
//输出max(pos,neg)
return 0;
}
blablabla