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-23增量更新怎么做?-icode9专业技术文章分享
- 2024-11-23压缩包加密方案有哪些?-icode9专业技术文章分享
- 2024-11-23用shell怎么写一个开机时自动同步远程仓库的代码?-icode9专业技术文章分享
- 2024-11-23webman可以同步自己的仓库吗?-icode9专业技术文章分享
- 2024-11-23在 Webman 中怎么判断是否有某命令进程正在运行?-icode9专业技术文章分享
- 2024-11-23如何重置new Swiper?-icode9专业技术文章分享
- 2024-11-23oss直传有什么好处?-icode9专业技术文章分享
- 2024-11-23如何将oss直传封装成一个组件在其他页面调用时都可以使用?-icode9专业技术文章分享
- 2024-11-23怎么使用laravel 11在代码里获取路由列表?-icode9专业技术文章分享
- 2024-11-22怎么实现ansible playbook 备份代码中命名包含时间戳功能?-icode9专业技术文章分享