本文共 1379 字，大约阅读时间需要 4 分钟。

题目链接:

题目描述

给定一个长度为 n 的数列a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。

输入格式

第一行输入正整数n。

输出格式

第一行输出最少操作次数。

数据范围

0<n≤10^5, 0≤ai<2147483648

输入样例

4

1

1

2

2

输出样例

1

2

解题思路

首先我们来介绍一下差分是什么东西:

1. 差分定义

• 定义一个差分数组S和一个原数组A。
• p[1]=a[1], p[i]=a[i]-a[i-1]

2. 差分性质

• A数组的差分数组的前缀和数组就等于原数组,即S[i]=a[i]=p[i]+S[i-1]
• S数组的差分数也等于差分数组，即p[i]=S[i]-S[i-1]
• 还有比较重要，而且常用的的一条，我们在修改某一段区间的时候，比如这道题的集体加 e 的时候，将操作放在差分数组上就变成了p[l]+=e,p[r+1]-=e这样，我们就可以把区间操作更改为单点操作，很大的减少了时间复杂度。
• 当然，差分的运用远不止于此，在树上等也是可以进行差分操作的。

综上：有了这些性质，我们在做一些题的时候就可以将其转换为差分数组求解，完成过后过一遍前缀和得到正确答案。

说了这么多，就来看看这一题怎样做吧。 

3. 本题题解

• 因为是区间整体加减1，所以我们很自然的就可以想到用差分求解。
• 这道题可以看做求出原序列的差分之后，将差分数组p[2...n]全部变为0所需的最少的步数和可以使p[1]变为多少种不同的数。
• 贪心操作: 很明显，在我们求出的差分数组中，有正数也有负数，要消除这些数，使得它们全部归零。，我们可以让正数减1，负数加1，这样就可以快速的转化成目标0。有可能pos!=neg,那么就让剩余的和p[1]或p[n+1]配对。
• 经过上述分析，我们就能够推导出本题的最小次数公式:
• ans=min(pos,neg)+abs(pos-neg)=max(pos,neg);
• 最后我们还要求能构成几组解, 这很容易可以推出: ans=abs(pos-neg)+1

Accepted Code:​​​​​​​

#include 
   
    using namespace std;int main() {    int a, b, n, cnt;    long long pos = 0, neg = 0;    scanf("%d", &n);    scanf("%d", &a);    for (int i = 1; i < n; i++) {        scanf("%d", &b);        cnt = b - a;        if (cnt > 0)            pos += cnt;        else neg -= cnt;        a = b;    }    printf("%lld\n%lld\n", max(pos, neg), llabs(pos - neg) + 1);    return 0;}
   

转载地址：https://lzyws739307453.blog.csdn.net/article/details/92075599 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！