C/C++教程

AcWing 100. 增减序列

本文主要是介绍AcWing 100. 增减序列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目传送门

一、试题分析

因为题意要求,每次都一个区间加上1或者减去1,所以想到了差分。

首先,先对数组\(a\)差分一下,求出差分数组\(b\),接下来我们的任务就是对\(b[2\sim n]\)全部变成\(0\)(所有的数和\(b[1]=a[1]\)一样)即可。

我们对差分序列\(b\)直接操作,因为一个\(++\),一个\(--\),所以我们在\(2 \sim n\)之间要选择一个正数一个负数,一个\(--\),一个\(++\),这样就可以尽可能较少操作步骤,剩下的就和\(b[1]\)或者\(b[n+1]\)抵消(不影响整体结果)。

\(p\)为\(b\)当中正数的和。

\(q\)为\(b\)当中负数绝对值的和。

操作步骤\(=min(p,q)+abs(p-q)\)

因为最后可以选择\(b[1]\)或者\(b[n+1]\)抵消,

比如\(b=1   0   2  0\)

它可以有
\(3 0 0 0\)(全部和\(b[1]\)消除)
\(2 0 0 0\) (一个\(b[1]\),一个\(b[n+1]\))
\(1 0 0 0\)(全部\(b[n+1]\))

结果数量=\(abs(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() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &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;
}
这篇关于AcWing 100. 增减序列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!