算法1
(差分) $O(n)$
对于一段操作同时+1 /-1, 这个时候想到差分 , 令a[i] = p[i] - t[i] , 表示要变化的温度值 , 那么对其进行差分 , 使差分数组变为0 , 即可使a[i]=0(1<=i<=n) ;
对差分数组有两种操作类型 :
– 任选一个 + 1 , 然后再任选一个-1
– 任选一个 + 1 / - 1
那么分别统计+/-两者较大值即可 ;
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10 ;
int p[N] , t[N] ;
int a[N] ;
int main(){
int n ; 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++){
a[i] = p[i] - t[i] ;
}
// 差分
for(int i=n;i>1;i--) a[i] -= a[i-1] ;
int x = 0, y = 0 ;
for(int i=1;i<=n;i++){
if(a[i] > 0) x+= a[i] ;
else y -= a[i] ;
}
cout << max(x , y) << endl ;
}
群猪大大😍