csp信奥赛C高频考点专项训练之前缀和差分 --【一维差分】IncDec Sequence题目描述给定一个长度为n nn的数列a 1 , a 2 , ⋯ , a n {a_1,a_2,\cdots,a_n}a1,a2,⋯,an每次可以选择一个区间[ l , r ] [l,r][l,r]使这个区间内的数都加1 11或者都减1 11。请问至少需要多少次操作才能使数列中的所有数都一样并求出在保证最少次数的前提下最终得到的数列有多少种。输入格式第一行一个正整数n nn。接下来n nn行每行一个整数第i 1 i1i1行的整数表示a i a_iai。输出格式第一行输出最少操作次数。第二行输出最终能得到多少种结果。输入输出样例 #1输入 #14 1 1 2 2输出 #11 2说明/提示对于100 % 100\%100%的数据n ≤ 100000 n\le 100000n≤1000000 ≤ a i ≤ 2 31 0 \le a_i \le 2^{31}0≤ai≤231。思路分析本题要求通过区间加减1操作使数组所有元素相等并求最少操作次数及可能的结果种数。关键技巧差分。定义差分数组 (d 1 a 1 d_1 a_1d1a1)(d i a i − a i − 1 ( i ≥ 2 ) d_i a_i - a_{i-1}\ (i\ge 2)diai−ai−1(i≥2))。操作 ([l, r]) 加1 等价于 (d l ← d l 1 , d r 1 ← d r 1 − 1 d_l \leftarrow d_l1,\ d_{r1} \leftarrow d_{r1}-1dl←dl1,dr1←dr1−1)当 (rn)若 (rn) 则只影响 (d l d_ldl)。最终所有 (a i a_iai) 相等 等价于 (d 2 d 3 ⋯ d n 0 d_2d_3\dotsd_n0d2d3⋯dn0)。设 (p ∑ i 2 n max ( d i , 0 ) p \sum_{i2}^n \max(d_i,0)p∑i2nmax(di,0))正数和(q ∑ i 2 n max ( − d i , 0 ) q \sum_{i2}^n \max(-d_i,0)q∑i2nmax(−di,0))负数绝对值和。每次操作可以同时减少一个正数和一个负数配对操作消耗一步单独减少一个正数或单独增加一个负数边界操作使用 ([l,n]) 区间也消耗一步。因此最少操作次数为 (max ( p , q ) \max(p,q)max(p,q))。剩下的 ( |p-q| ) 次操作只能单独进行若剩下正数则做 ( |p-q| ) 次减操作若剩下负数则做 ( |p-q| ) 次加操作。每次单独操作可以选择在位置 (1)影响最终值或其它位置不影响。最终 (a 1 a_1a1) 的改变量有 ( |p-q|1 ) 种可能即最终数列有 ( |p-q|1 ) 种不同的值。代码实现#includebits/stdc.husingnamespacestd;typedeflonglongll;intmain(){intn;cinn;ll a,b;cina;// a 记录前一个数ll p0,q0;for(inti2;in;i){cinb;ll db-a;// 差分if(d0)pd;elseq-d;// d为负累加其绝对值ab;}ll ans1max(p,q);ll ans2abs(p-q)1;coutans1\nans2\n;return0;}功能分析输入处理读取 (n) 和第一个数 (a)循环读入后续 (n-1) 个数实时计算差分。核心计算累加正差分 (p) 和负差分的绝对值 (q)。输出最少操作次数 (max ( p , q ) \max(p,q)max(p,q))最终结果种数 (|p-q|1)。时间复杂度O(n)空间 O(1)满足 (n ≤ 10 5 n\le 10^5n≤105) 要求。【完整系列请查看专栏】信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C提高组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}
