贪心、差分
考虑长度为 $n$ 的差分数组 $d$,其中 $d_i = d_{i} - d_{i-1}$。这里认为 $d_0 = 0$。
进行一步转化:区间 $+1$ 等价于在差分序列 $d$ 中选择 $d_i$ 使其 $+1$,然后视情况选择 $d_j \ (i<j)$ 使其 $-1$(不选择实质上是对 $a_i \sim a_n$ 做了 $+1$ 操作)。区间 $-1$ 的情况恰好相反。
最终目标是 $\forall i \in [2,n],d_i = 0$,无关 $d_1$ 的值。
考虑配对,每次找一个大于 $0$ 的值 $d_i$ 和一个小于 $0$ 的值 $d_j$,通过执行操作使得 $d_i \leftarrow d_i - 1$,$d_j \leftarrow d_j + 1$,注意这里 $i,j \geq 2$,不断执行操作直到无法配对为止。
最好情况是已经达成最终目标,否则 $d_2 \sim d_n$ 里必定有一些值为正(负),同时没有任何负(正)值。对于这些值,使用 $d_i$ 表示它们,有两种解决方式。这里假设 $d_i >0$:
- 用 $d_1$ 和 $d_i$ 配对,因为 $d_1$ 可以随意操作。
- 对 $a_i \sim a_n$ 执行 $-1$ 操作,这样只会改变 $d_i$ 的值。
如果用 $d_1$ 配对,就能改变达成目标后 $a_1 \sim a_n$ 的值,因此可以求出第二问的答案。
统计 $d_2 \sim d_n$ 中正整数的和记为 $posi$,负整数的和的绝对值记为 $nega$,第一问答案为 $\max(posi,nega)$,第二问答案为 $|posi-nega| + 1$。
时间复杂度 $O(n)$。
#include<bits/stdc++.h>
using namespace std;
long long ans,posi,nega,a[100'005],d[100'005];
int n;
int main(){
ios::sync_with_stdio(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) d[i]=a[i]-a[i-1];
for(int i=2;i<=n;i++){
if(d[i]>0ll) posi+=d[i];
if(d[i]<0ll) nega-=d[i];
}
cout<<max(posi,nega)<<'\n'<<abs(posi-nega)+1<<'\n';
return 0;
}