贪心、差分

考虑长度为 $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;
}
最后修改:2024 年 12 月 19 日
如果觉得我的文章对你有用,请随意赞赏