题意:
给出一数组,已知一次操作可以让一个区间内的数加一或减一,求使得数组内所有元素一致的最少操作数和方案数
解题思路:
1.区间的加减可以用差分来完成,那么使数组内元素一致即可以看成令差分数组内所有元素为零
2.因为一次区间操作可以让差分数组内一个元素+1,一个元素-1或是只取一个元素+1/-1,统计差分数组内所有负值(绝对值)和正值,可以推出最少操作数应该为两个统计值中的最大值,而方案数则为两个统计值的差+1
代码如下:
#include <bits/stdc++.h>
#include<algorithm>
using namespace std;
#define ll long long
#define N 100005
ll a[N],b[N],x,y;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
//差分数组
if(i)b[i] = a[i]-a[i-1];
//分别统计其中的正值和负值
if (b[i] > 0)x += b[i];
else y -= b[i];
}
cout << max(x, y) << endl << abs(x - y) + 1;
}