python

6.8 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##AcWing 100. 增减序列

一、题目描述

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

求至少需要多少次操作才能 使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

输入格式 第一行输入正整数 n。

接下来 n 行，每行输入一个整数，第 i+1 行的整数代表 a_i。

输出格式

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

第二行输出最终能得到多少种结果。

数据范围 0<n≤10^5,0≤a_i<2147483648

输入样例：

输出样例：

1
2

二、题目解析

差分复习

对于一个给定序列 a, 它的差分序列 b 定义为：

  b[1]=a[1] ① \\  b[i]=a[i]−a[i−1]  (2≤i≤n)②

可以发现， 前缀和 、差分是一对互逆运算，b 序列的前缀和就是 a 序列。

应用如果要把序列 a 的 [l,r] 区间内的所有数加 d，差分序列 b 的变化为 b[l] 加 d，b[r+1] 减 d,减法同理。

本题思路

因为题目中提到在原数组 a[i]的某个区间上要么加1，要么减1,也就是一维数组的区间加减问题，符合差分的应用场景,使用差分，可以使得原来r-l+1次修改变成2次，可以节约大量的计算时间，所以，本题应该考虑使用差分。

那我们就需要求出 a 的差分序列 b。

题目的最终目标是把数组的全部数字变成一样的，那么，对应到差分数组，就是 b[1],b[n+1]是什么值都可以，但b[2],b[3],...b[n]都需要等于0，并且，b[1]的值就是最终数组a[]的所有数字一样的那个值。

以数据样例为例进行理解

原始数组：    1 1 2 2
差分数组:     1 0 1 0

A方案，前两个+1:2 2 2 2 差分数组随之变化,1位加1，2+1=3位减1,得到如下的差分数组：

2 0 0 0

B方案，后两个-1:1 1 1 1 差分数组随之变化,3位减1，4+1=5位加1,得到如下的差分数组：

1 0 0 0 1

咦？为什么原数组是4个数字，你的差分是5个数字呢?

你看一下上面的应用a[l-r]加上d,是不是b[l]+=d,b[r+1]-=d,而1<=l<=r<=n 考虑一下边界问题，如果 r=n时，上面的

b[r+1]-=d \Rightarrow b[n+1]-=d

也就是说，b[]数组需要考虑到n+1项，此时，如果r=n时，也就是变化区间最右边到n时，就用到了b[n+1],但b[n+1]最终是什么值不重要，它的值不影响区间内所有元素的值一样。

贪心思路求变化最小次数

转化：题目对 a 序列的 任何区间加减1操作，等同于对 b 序列中的 任意两数，一个加 1，一个减 1。目标 : 把 b[2] 至 b[n] 全变为 0,b[1],b[n+1]是多少无所谓。

从 b[1] 至 b[n+1] 中任选两数的方案进行分类讨论：

由于b[1],b[n+1]比较特殊，所以划分分类时，以它们为分类标准进行划分四类：

① 选 b[i] 和 b[j] 其中 2≤i,j≤n，这种操作会改变 b[2] 至 b[n] 中两个数的值，因为差分操作，无外乎就是：
- 前项+1，后项-1
- 前项-1，后项+1 这两种情况，目标是把这段区间所有数字变成0,那大于0的得-1向小了变，小于0的得+1向大的变。也就是尽量挑 b[i] 和 b[j] 一正一负 的情况下，这样一下就可以 变掉两个数，使得整体向都是0的区间逼近。
② 选 b[1] 和 b[j] 其中 2≤j≤n；这种情况下也是两种可能分支:
- b[j]>0,那么b[j]-=1,b[1]+=1
- b[j]<0,那么b[j]+=1,b[1]-=1 因为我们并不关心b[1]的最终值是多少，只关心尽快的把b[2 \sim n]变成0,所以，这样一下只能改一个数字，效率不如上面的 ① 快。
③ 选 b[i] 和 b[n+1] 其中 2≤j≤n；这种情况下也是两种可能分支:
- b[i]>0,那么b[i]-=1,b[n+1]+=1
- b[i]<0,那么b[i]+=1,b[n+1]-=1 因为我们并不关心b[n+1]的最终值是多少，只关心尽快的把b[2 \sim n]变成0,所以，这样一下只能改一个数字，效率不如上面的 ① 快。
④ 选 b[1] 和 b[n+1] 因为它不会改变 b[2] 至 b[n] 的值，浪费了操作，一定不是最优解,放弃这种可能。

所以，我们的贪心策略就是：尽量的采用方法 ①,如果实在没有办法使用方法 ①时，再考虑使用方法 ② 或者方法 ③。

那什么情况下可以使用方法 ① 呢？限制条件是在b[2 \sim n]中存在1个及1个以上大于0的数字，并且，存在1个及1个以上小于0的数字，才能进行此操作。

所以，有了如下的神操作：

设 b[2] 至 b[n] 中正数总和为 p，负数总和的绝对值为 q。

首先，我们以正负配对的方式执行操作，可执行 min(p,q) 次，剩余 |p−q| 个没有配对。

接下来，剩下的每个与 b[1] 或 b[n+1] 配对，共需 |p−q| 次。

综上，最少操作次数为 min(p,q)+|p−q|=max(p,q) 次。

下面来思考第二个问题：

保证最少次数的前提下，最终得到的数列可能有多少种?

答：在尽量采用方法 ① 的情况下，可以尽快的使得整体区间向全是0进行逼近，但最后，随着正数或者负数的消亡，剩下了|p-q|个正数值或者负数值，此时，只能通过与b[1]或 b[n+1]的捉对操作才能完成整体全是0的目标

假设剩下|p-q|个：

b[1]消耗掉0个，|p-q|个交给b[n+1]消耗掉
b[1]消耗掉1个，|p-q|-1个交给b[n+1]消耗掉
b[1]消耗掉2个，|p-q|-2个交给b[n+1]消耗掉 ...
b[1]消耗掉|p-q|个，0个交给b[n+1]消耗掉
共有|p-q|+1种情况，此时，b[1]的值也随之变化，共|p-q|+1种结果。

三、实现代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;

int n;
int a[N], b[N];

int main() {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i] - a[i - 1];
    }

    LL p = 0, q = 0;
    for (int i = 2; i <= n; i++)
        if (b[i] > 0)
            p += b[i];
        else
            q -= b[i];

    printf("%lld\n%lld\n", max(p, q), abs(p - q) + 1);
    return 0;
}

6.8 KiB Raw Permalink Blame History Unescape Escape