IncDec Sequence

链接

既然题目要求最终所有数字都要相等,是不是意味着所有数字只差为0?

依据于此,我们可以创建一个长度为n的数组,第一个元素就是题目输入的第一个值,往后都是差值

比如2 3 4 5 7 4得到的结果是2 1 1 1 2 -3目标(? 0 0 0 0 0,第一个元素不确定)

我们对区间[l,r]进行操作,会发现新数组l和r+1的元素进行了改变,l的改变与操作相同,r+1则相反

特别的,如果r位于最后一位,那么新数组只有l进行了更改

我们发现了规律:操作时新数组只有至多两个元素改变,而且两个元素改变相反(一个加一,另一个减一),如果只改变一个元素,我们可以进行加一或减一

不难想到,同时对正数负数操作是最快的,刚刚那个数组我们可以让前面的整数减一,后面的负数加一

这样,我们操作3次可以得到 2 0 0 0 2 0(当然2 1 1 0 0 0也行,只要满足第一个元素后面相加为2即可),此时我们可以更改两个也可以更该一个(更改两个是第一个元素加一,后面的2减一,更改一个是后面的2减一,第一个不变)

不难看出,最终答案有3种(均为2,3或4),更改次数为3+2=5种

总结规律,更改次数为第一个元素之后的正数和与负数和的最大值,即max(正数,|负数|), 种数为(|正数-|负数||+1)

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    
    vector<long long>num(n),diff(n);
    for(int i=0;i<n;i++){
       cin>>num[i];
        if(i==0)diff[i]=num[i];
        else diff[i]=num[i]-num[i-1];
    }
    long long sum=0,negative=0;
    for(int i=1;i<n;i++){
        sum+=abs(diff[i]);
        negative+=diff[i]<0?-diff[i]:0;
    }
    cout<<max(sum-negative,negative)<<endl;
    cout<<abs(sum-2*negative)+1<<endl;
    
}

时间复杂度:O(n)

空间复杂度:O(n)