喜欢就点个赞👍呗,每天都会更新哦!^-^
Problem:
将一个数组t变成数组a,你可以操作一个连续数组,让数组每一个元素+1或者-1,求最小操作次数
Ideas:
首先,对一个区间进行统一操作,差分无疑是最好的选择,但是怎么差分呢?
让一个数组变成另外一个数组,那么就会有一个变化量,也就是说,可以从每一个元素从该状态到另外一个状态,差值是多少,就是它们的一个变化量,那么,如何让这个变化量数组发生变化呢,就是说我要通过操作变化量数组让它们的值变成一样,到目前为止还没有使用过差分,我们对该变化量数组进行差分,我们要得到什么?得到一个变化量全为0的数组,也就是差分也为0的数组(因为变化量数组就是差分的前缀和)
其次,看看差分的性质是什么:
差分让一个左区间+1, 然后让一个右区间-1,就能够实现让这个区间都+1,反之,可以让这个区间都-1,但是这个不是这个题目的重点,重点是:
它可以让一个数-1,然后让一个数+1,那么,我们可以让变化量数组中的所有负数+1,所有正数-1,然后取负数的绝对值之和和正数之和的max即可,为什么,有人可能有疑问在一个点:
如果正数和负数和不一样大,让一个数+1,一个数-1就会出现问题,加入负数用完了,只剩下正数,此时我们可以让一个不在1~n的位置-1呀,换而言之,让从这个正数开始的位置,到整个数组结束,都-1
Ideas:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
void solve() {
int n;
cin >> n;
int a[N]; // 用一个数组来表示变化量即可
for(int i = 0; i < n; i ++ ) cin >> a[i];
for(int i = 0; i < n; i ++ ) {
int x;
cin >> x;
a[i] -= x; // 得到变化量
}
for(int i = n - 1; i > 0; i -- ) a[i] -= a[i - 1]; // 差分变化量
int x = 0, y = 0; // 记录正数和负数
for(int i = 0; i < n; i ++ ) {
if(a[i] > 0) x += a[i];
else y -= a[i];
}
cout << max(x, y) << endl;
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0);
cout.tie(0);
int t = 1;
while(t -- ) {
solve();
}
}
正数和负数的绝对值不应该是相等的吗?
不一定都相等,例如样例里的那个差分就是0,3,-2,0,2。正数的和就是5,负数的绝对值就是2,它应该就是取最大的值。应该是这样的吧~~