AcWing 100 增减序列

2022/1/24 6:06:05

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

题目

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

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

分析

对于区间加减的问题,可以考虑用差分数列解决

设 \(b_i=a_i-a_{i-1}\) ,那么选择一个区间 \([l,r]\) 加 \(1\) 就等价于 \(b_l+1,b_{r+1}-1\) ,区间减 \(1\) 就等价于 \(b_l-1,b_{r+1}+1\)

所以问题转化为了 从 \(b_1,b_2,\cdots,b_{n+1}\) 中任意选出两项,一项加 \(1\) ,另一项减 \(1\),若干步后使 \(b_2=b_3=\cdots=b_n=0\)

任选两个项的方法有四种:

  • \(b_i,b_j,2\leq i,j\leq n\)
  • \(b_1,b_j,2\leq j \leq n\)
  • \(b_i,b_{n+1},2\leq i \leq n\)
  • \(b_1,b_{n+1}\)

而第四类方法只会浪费步骤,所以不考虑

第一种方法在一正一负的情况下可以一次改变两个数的值,应该尽可能采取这种方法

当无法采用第一种方法时,可以采用第二种或第三种

设 \(p\) 为 \(b_1,b_2,\cdots,b_n\) 中的正数项总和, \(q\) 为负数项总和的绝对值,即:

\[p=\sum_{i=2}^n \max(b_i,0),q=|\sum_{i=2}^n \min(b_i,0)| \]

正负数配对可执行 \(\min(p,q)\) 次方法1,而剩下的数则执行方法2或方法3,一共 \(\min(p,q)+|p-q|=\max(p,q)\) 次

根据方法2和方法3的选取情况,能产生 \(|p-q| + 1\) 种 \(a_1\)

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int n;
ll a[100000 + 5];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    ll p = 0, q = 0;
    for(int i = 2; i <= n; i++) {
        p += max(a[i] - a[i - 1], 0ll);
        q += abs(min(a[i] - a[i - 1], 0ll));      
    }
    printf("%lld\n%lld\n", max(p, q), abs(p - q) + 1);
    return 0;
}


这篇关于AcWing 100 增减序列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程