Cidoai的听歌时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述C i d o a i CidoaiCidoai喜欢听歌。它拿到了一个长为n nn的数列a 1 , a 2 , ⋯ , a n a_1,a_2,⋯ ,a_na1​,a2​,⋯,an​。C i d o a i CidoaiCidoai会循环进行以下两种操作从操作1 11开始选择数列中任意多个数 1 11;选择数列中任意多个数− 1 -1−1。单次操作中必须选择不同位置的数。它都希望使用最少的操作次数使得整个数列都相等求最少的操作次数以及整个数列最后等于的数可以证明在最少操作次数的时候整个数列最后等于的数唯一。输入描述第一行一个正整数n nn。第二行n nn个整数分别表示a 1 , a 2 , ⋯ , a n a_1,a_2,⋯ ,a_na1​,a2​,⋯,an​。1 ≤ n ≤ 10 6 , 1 ≤ a i ≤ 10 9 1≤n≤10^6,1≤a_i≤10^91≤n≤106,1≤ai​≤109。输出描述一行两个整数分别表示最少的总操作次数和整个数列最后等于的数。示例1输入8 3 2 4 5 2 3 4 2输出3 4说明一开始的数列为[ 3 , 2 , 4 , 5 , 2 , 3 , 4 , 2 ] [3,2,4,5,2,3,4,2][3,2,4,5,2,3,4,2]。C i d o a i CidoaiCidoai选择a 2 , a 5 , a 8 a_2,a_5,a_8a2​,a5​,a8​操作第一次后可变为[ 3 , 3 , 4 , 5 , 3 , 3 , 4 , 3 ] [3,3,4,5,3,3,4,3][3,3,4,5,3,3,4,3]。选择a 4 a_4a4​操作第二次后可变为[ 3 , 3 , 4 , 4 , 3 , 3 , 4 , 3 ] [3,3,4,4,3,3,4,3][3,3,4,4,3,3,4,3]。选择a 1 , a 2 , a 5 , a 6 , a 8 a_1,a_2,a_5,a_6,a_8a1​,a2​,a5​,a6​,a8​操作第三次后可变为[ 4 , 4 , 4 , 4 , 4 , 4 , 4 , 4 ] [4,4,4,4,4,4,4,4][4,4,4,4,4,4,4,4]。一共操作了3 33次最后得到的数为4 44。解题思路本题是交替操作下的数组均衡问题最终目标是将数组中的所有数通过一系列交替的 1 11和− 1 -1−1操作变为同一个值并使总操作次数最少。可以证明最优解只与数组的最大值和最小值有关最少操作次数即为两者之差最终相等的数值为两者均值的上取整。1. 问题等价转化操作序列从 1 11开始交替进行− 1 -1−1、 1 11……每次操作可以任选一个子集进行统一的 1 11或− 1 -1−1但同一次操作中不能对同一位置重复选择。设最终所有数变为x xx第i ii个数初始为a i a_iai​。它被 1 11的次数记为p i p_ipi​被− 1 -1−1的次数记为q i q_iqi​则有a i p i − q i x a_i p_i - q_i xai​pi​−qi​x即p i − q i x − a i p_i - q_i x - a_ipi​−qi​x−ai​。设总操作次数为T TT由于从 1 11开始交替进行总 1 11次数P ⌈ T / 2 ⌉ P \lceil T/2 \rceilP⌈T/2⌉总− 1 -1−1次数Q ⌊ T / 2 ⌋ Q \lfloor T/2 \rfloorQ⌊T/2⌋。存在合法方案等价于对每个i ii都能分配0 ≤ p i ≤ P 0 \le p_i \le P0≤pi​≤P0 ≤ q i ≤ Q 0 \le q_i \le Q0≤qi​≤Q且满足上述差值。最紧的约束来自需要最大增加量和最大减少量的数必须满足P ≥ max ⁡ i ( x − a i ) x − min ⁡ a P \ge \max_i (x - a_i) x - \min aP≥maxi​(x−ai​)x−minaQ ≥ max ⁡ i ( a i − x ) max ⁡ a − x Q \ge \max_i (a_i - x) \max a - xQ≥maxi​(ai​−x)maxa−x。2. 最优解推导由P ≥ x − min ⁡ a P \ge x - \min aP≥x−mina和Q ≥ max ⁡ a − x Q \ge \max a - xQ≥maxa−x相加得T P Q ≥ ( x − min ⁡ a ) ( max ⁡ a − x ) max ⁡ a − min ⁡ a T P Q \ge (x - \min a) (\max a - x) \max a - \min aTPQ≥(x−mina)(maxa−x)maxa−mina因此T TT至少为max ⁡ a − min ⁡ a \max a - \min amaxa−mina。下面证明该下界总是可达并给出对应的x xx若max ⁡ a − min ⁡ a \max a - \min amaxa−mina为偶数令T max ⁡ a − min ⁡ a T \max a - \min aTmaxa−mina则P Q T / 2 P Q T/2PQT/2。此时要求x ≤ min ⁡ a T / 2 x \le \min a T/2x≤minaT/2且x ≥ max ⁡ a − T / 2 x \ge \max a - T/2x≥maxa−T/2两者均等于( max ⁡ a min ⁡ a ) / 2 (\max a \min a)/2(maxamina)/2故x xx唯一确定为该平均值整数。若max ⁡ a − min ⁡ a \max a - \min amaxa−mina为奇数令T max ⁡ a − min ⁡ a T \max a - \min aTmaxa−mina则P ( T 1 ) / 2 P (T1)/2P(T1)/2Q ( T − 1 ) / 2 Q (T-1)/2Q(T−1)/2。此时约束给出x ⌈ ( max ⁡ a min ⁡ a ) / 2 ⌉ x \lceil (\max a \min a)/2 \rceilx⌈(maxamina)/2⌉。同样可达。综上最少操作次数固定为max ⁡ a − min ⁡ a \max a - \min amaxa−mina最终数值固定为⌈ ( max ⁡ a min ⁡ a ) / 2 ⌉ \lceil (\max a \min a)/2 \rceil⌈(maxamina)/2⌉在整数运算中可统一写为( max ⁡ a min ⁡ a 1 ) / 2 (\max a \min a 1)/2(maxamina1)/2。3. 算法实现读取数组求最大值m x mxmx和最小值m n mnmn。输出m x − m n mx - mnmx−mn和( m x m n 1 ) / 2 (mx mn 1) / 2(mxmn1)/2整数除法自动下取整加1 11实现上取整效果。4. 复杂度分析时间复杂度O ( n ) O(n)O(n)仅需一次遍历。空间复杂度O ( 1 ) O(1)O(1)无需存储整个数组。总结巧妙地将交替加减操作转化为对最大增加量和最大减少量的容量限制直接推导出操作次数下界为极差并确定最终目标值为极值均值的上取整。算法极简在线性时间内即可得出答案。代码简要说明读入n nn初始化m x 0 mx 0mx0m n 10 9 mn 10^9mn109。遍历所有x xx更新m x mxmx和m n mnmn。输出m x − m n mx - mnmx−mn和( m x m n 1 ) / 2 (mx mn 1) / 2(mxmn1)/2。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;cinn;ll mx0,mn1000000000LL;for(ll i1;in;i){ll x;cinx;mxmax(mx,x);mnmin(mn,x);}cout(mx-mn) (mxmn1)/2endl;return0;}