算法竞赛进阶指南-0x03-前缀和与差分-增减序列

xuezhiyu · 2023-12-23 09:33:43 · 个人记录

题目

题目描述

给定一个长度为 n \space (n \le 10^5) 的数列 a_1,a_2,\cdots,a_n，每次操作可以选择一个区间 [l,r] 然后把在这个区间内的数字就加一或减一。

求最少多少步内可以让数列中所有数字一样大，并在保证最少次数的前提下，最终得到的数列能够有多少种。

输入格式

第 1 行一个整数 n ，代表数列的长度。

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

分析题目

这道题如果通过暴力 dfs 的话，第一个点估计都过不去，所以说就要用一些奇妙的算法了。

介绍一种非常简单的算法：

差分

差分，就是一个数列中第 i 项和第 i-1 的差，一般记作 B。

一个数列 A 的差分序列 B 可以表示为：

一般为了方便计算，还会让 B_{n+1}=0。

把数列 A 的区间 [l,r] 之间加上一个数 p （即把 A_l,A_l+1,\cdots,A_r 都加上 p），它的差分序列 B 的变化就是把 B_l 加上 p，然后 B_{r+1} 减去 p。

这道题中让数列中所有数相同，其实就是让 B_2,B_3,B_4,\cdots,B_n 全部变为 0 。题目中对于数列 A 的操作，相当于每次从 B_1,B_2,\cdots,B_{n+1} 中选出两个数，然后一个加 1 ，一个减 1。

那么这道题的话，就要先尽量地寻找一正一负的两个数，然后负的数加 1，正的数减 1；然后再把剩下不是 0 的数和 B_1 或 B_{n+1} 匹配，然后就可以把整个差分数列全部变成 0。

令 p 等于整个差分序列中正数的和，p 等于整个差分序列中负数的绝对值的和，那么第一种操作（寻找一正一负的两个数）就可以执行 \min(p,q) 次，第二种操作（和 B_1 和 B_{n+1} 匹配）就需要执行 |p-q| 次，一共的执行次数就是

而最终的得到的序列的种类数是要保证最小步数的，所以第一种操作都是一样的，第二种操作根据和 A_1 的匹配次数就有 |p-q|+1 种。

所以说第一个问的答案就是 \max(p,q)，第二个问的答案就是 |p-q|+1 种。

注意！，要开 long long！

代码时间

#include <cmath>
#include <iostream>
#define endl '\n'

using namespace std;

const long long N = (long long)1e5 + 5ll;
long long n, last, in, temp, p, q;

int main() {
    cin >> n >> last;
    for (long long i = 1ll; i < n; i++) {
        cin >> in;
        temp = in - last;
        if (temp > 0ll) p += temp;
        if (temp < 0ll) q -= temp;
        last = in;
    }
    cout << max(p, q) << endl;
    cout << abs(p - q) + 1ll;
    return 0;
}