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 增减序列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-15Typescript 类型教程:轻松入门与实践指南
- 2024-11-15AntDesign-icons项目实战:新手入门教程
- 2024-11-14用Scratch编写语言模型:爪爪(Clawed)式简易教程
- 2024-11-14用大型语言模型在Amazon Bedrock上分类Jira工单
- 2024-11-14从数据到行动:亚马逊Bedrock代理如何自动化复杂工作流
- 2024-11-14Databricks与优化后的Snowflake性能大比拼
- 2024-11-14亚马逊 Inspector 解析:提升您的 AWS 负载安全的利器
- 2024-11-14揭秘VS Code for Web - Azure:轻松开发云端应用的新利器
- 2024-11-14揭秘指南:如何让Databricks中的数据为最终用户所用
- 2024-11-14OpenTelemetry扩展进入CI/CD可观测性领域