上海计算机学会2026年月6月赛C++丙组T5 温度校准

温度校准题目描述在一个房间里有NNN个位置每个位置上有一个数字表示这个位置的温度偏差其中第iii个位置的温度偏差为AiA_iAi​AiA_iAi​可正可负。房间里有一台空调我们的目的是通过控制空调消除所有温度偏差。这台空调可以选择两个模式制冷或制热以及一个强度参数xxxxxx至少为111至多为NNN。如果选择制冷模式再设定xxx之后空调开始运行经过一小时后最后一个位置的温度下降xxx度倒数第二个位置的温度下降x−1x-1x−1度倒数第三个位置的温度下降x−2x-2x−2度……倒数第xxx个位置的温度会下降111度其他位置保持温度不变。如果选择制热模式除了温度从下降改成上升之外与制冷模式没有区别。空调可以以不同模式、不同强度运行任意多个小时。请问最少需要多少小时才能让所有位置的温度偏差调成零。输入格式第一行单个整数NNN。第二行NNN个整数A1,A2,…,ANA_1, A_2, \dots, A_NA1​,A2​,…,AN​。输出格式单个整数表示最少需要的小时数。数据范围对于 30% 的数据1≤n≤101 \le n \le 101≤n≤10对于 60% 的数据1≤n≤1,0001 \le n \le 1,0001≤n≤1,000对于 100% 的数据1≤n≤1,000,0001 \le n \le 1,000,0001≤n≤1,000,000−109≤ai≤109-10^9 \le a_i \le 10^9−109≤ai​≤109样例样例1输入2 -1 1输出4题目来源改编自 USACO 2024 Jan, Balancing Bacteria好的我将按照您的要求把题解中的所有数学公式改为用$包围的 LaTeX 格式行内公式用$...$行间公式用$$...$$同时保持源代码和注释不变注释中原本没有公式。以下是修改后的完整题解。我的题解本题要求用最少的操作次数将所有温度偏差归零每次操作可选择制冷减或制热加强度为 (x)对最后 (x) 个位置分别施加递减的调节量从 (x) 到 (1)。通过分析这种操作对原数组的影响可以等价地描述为在二阶差分上的单点修改。定义原数组为AiA_iAi​令一阶差分DiAi−Ai−1D_i A_i - A_{i-1}Di​Ai​−Ai−1​规定A00A_0 0A0​0再令二阶差分EiDi−Di−1E_i D_i - D_{i-1}Ei​Di​−Di−1​规定D00D_0 0D0​0。一次强度为xxx的制冷操作减会使最后xxx个位置分别减去x,x−1,…,1x, x-1, \dots, 1x,x−1,…,1。考察其对二阶差分的影响设操作起始位置为pN−x1p N - x 1pN−x1从 1 开始编号它对位置ppp的减量为xxx对p1p1p1为x−1x-1x−1……对NNN为111。在二阶差分EEE上这个操作等价于在位置ppp处减111在位置p1p1p1处加111实际上因为减量递减差分和二阶差分的变化是局部的。经过推导一次操作只会使得某个EiE_iEi​增加111同时相邻的Ei1E_{i1}Ei1​减少111或反之取决于制冷/制热和方向。因此我们可以把每次操作看作是给二阶差分数组的某一个位置加111另一个位置减111。为了将所有EiE_iEi​变为零所需的最少操作次数就是所有EiE_iEi​的绝对值之和 —— 因为每个单位偏差需要一次操作来抵消且正负可以合并。于是问题转化为计算∑i1N∣Ei∣ \sum_{i1}^{N} |E_i|i1∑N​∣Ei​∣其中EiAi−2Ai−1Ai−2(A0A−10) E_i A_i - 2A_{i-1} A_{i-2} \quad (A_0 A_{-1} 0)Ei​Ai​−2Ai−1​Ai−2​(A0​A−1​0)代码中的循环正是高效地计算这个二阶差分并累加绝对值。变量sum用于累积当前位置之前所有操作的影响q数组存储了某种前缀和以便递推更新。整个算法时间复杂度O(N)O(N)O(N)空间O(N)O(N)O(N)完美适应N≤106N \le 10^6N≤106的数据范围。带注释的源代码#includebits/stdc.husingnamespacestd;intn;longlonga[1000005];// 存储原始温度偏差后续会被修改为二阶差分值longlongq[1000005];// 辅助数组用于递推更新 sumlonglongsum0;// 当前累积的修正量用于计算二阶差分longlongans0;// 最终答案最小操作次数intmain(){cinn;// 读入原始数组for(inti1;in;i){cina[i];}// 递推计算二阶差分 E[i]并累加绝对值for(inti1;in;i){// 对于 i 3需要减去 q[i-2]即前面二阶差分的前缀和if(i2)sum-q[i-2];// 减去 2 倍的前一个原始值实际上此时的 a[i-1] 已经变成了其自身的二阶差分// 但这里的 a[i-1] 在循环中已经被更新为二阶差分值// 通过递推关系这一步使得当前 a[i] 变为正确的 E[i]sum-a[i-1]*2;// 将累积修正加到当前 a[i] 上得到二阶差分 E[i]a[i]sum;// 将当前二阶差分的绝对值累加到答案ansllabs(a[i]);// 更新 q 数组q[i] 为前 i 个二阶差分之和用于后续的 sum 更新q[i]a[i]q[i-1];}// 输出最少操作次数coutans;return0;}