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)
查看21道真题和解析