【算法刷题】蓝桥杯：多次变化（位运算性质 + 贪心校验）

【算法刷题】蓝桥杯多次变化位运算性质 贪心校验 题目链接与描述题目名称多次变化题目链接蓝桥云课 - 多次变化数据规模1 ≤ n ≤ 10 5 1 \le n \le 10^51≤n≤1051 ≤ a r r i , n u m s i ≤ 10 5 1 \le arr_i, nums_i \le 10^51≤arri​,numsi​≤105核心问题给定长度为n nn的数组a r r arrarr和n u m s numsnums每次可挑连续 3 个数a , b , c a, b, ca,b,c若满足算式条件即可任意交换这三者的顺序。问能否将a r r arrarr转化为n u m s numsnums若能求对应位置差值的绝对值之和∑ i 0 n − 1 ∣ n u m s i − a r r i ∣ \sum_{i0}^{n-1} |nums_i - arr_i|∑i0n−1​∣numsi​−arri​∣若不能输出-1。 题目条件深度拆解为什么看不懂题目给出的原始条件是( ( a ∣ b ) ( a b ) ) m o d 2 c m o d 2 ((a \mid b) (a \ \ \ b)) \bmod 2 c \bmod 2((a∣b)(ab))mod2cmod21. 利用位运算恒等式化简根据计算机基础中的位运算恒等式( a ∣ b ) ( a b ) a b (a \mid b) (a \ \ \ b) a b(a∣b)(ab)ab直观理解按位或( a ∣ b ) (a \mid b)(a∣b)收集了两者出现过的所有1按位与( a b ) (a \ \ \ b)(ab)补上了重叠出现的1加起来正好等于普通的数值加法a b a bab。2. 转换成奇偶性判定将恒等式代入条件式子瞬间简化为( a b ) m o d 2 c m o d 2 (a b) \bmod 2 c \bmod 2(ab)mod2cmod2这说明只要( a b ) (a b)(ab)的奇偶性与c cc的奇偶性相同这 3 个连续的数就能任意交换顺序。分析奇偶组合奇 奇 偶→ \rightarrow→需要c cc是偶数组合奇, 奇, 偶偶 偶 偶→ \rightarrow→需要c cc是偶数组合偶, 偶, 偶奇 偶 奇→ \rightarrow→需要c cc是奇数组合奇, 偶, 奇3. 结论无条件自由重排只要数组里不是极致特殊的极端情况通常连续三个数的奇偶性都能自然凑出上述组合通过类似于冒泡排序的多次传导交换数组中的每一个元素都可以被挪动到任意位置。因此只要a r r arrarr和n u m s numsnums包含的元素种类与数量完全一致就一定能够转换成功 解题步骤备份与排序备份原始数组并将备份数组升序排序。可行性判断比较排序后的两个数组若有任何一位不相等a[i] ! b[i]说明元素对不上直接输出-1并结束程序。代价计算若元素完全一致无需考虑中间具体的交换过程直接计算未排序的原始数组在对应位置上的绝对值差值之和cost ∑ i 0 n − 1 ∣ n u m s [ i ] − a r r [ i ] ∣ \text{cost} \sum_{i0}^{n-1} |nums[i] - arr[i]|costi0∑n−1​∣nums[i]−arr[i]∣❌ 常见踩坑点数组未分配空间声明vectorint b;后未指定大小直接cin b[i]会导致内存越界崩溃Segmentation Fault。必须写成vectorlong long b(n);。算错代价的数组不能拿排序后的数组去算abs(a[i] - b[i])排序后的数组只用来校验元素一致性计算最终代价必须使用原始输入顺序的数组abs(nums[i] - arr[i])。数据溢出代价累加值可能超过2 31 − 1 2^{31}-1231−1必须使用long long存储。 最终 AC 代码 (C)#includebits/stdc.husingnamespacestd;intmain(){// 开启快速 I/Oios::sync_with_stdio(false);cin.tie(nullptr);intn;if(!(cinn))return0;vectorlonglonga(n),b(n);for(inti0;in;i)cina[i];for(inti0;in;i)cinb[i];// 1. 备份原数组vectorlonglongarra;vectorlonglongnumb;// 2. 对备份数组排序用于校验sort(arr.begin(),arr.end());sort(num.begin(),num.end());// 3. 检查元素是否完全匹配for(inti0;in;i){if(arr[i]!num[i]){cout-1\n;return0;// 无法转换直接退出}}// 4. 元素一致用原数组计算初始对应位置的代价和longlongsum0;for(inti0;in;i){sumabs(a[i]-b[i]);}coutsum\n;return0;}⏱️ 复杂度分析时间复杂度O ( n log ⁡ n ) \mathcal{O}(n \log n)O(nlogn)主要瓶颈在于对数组进行排序。对于n 10 5 n 10^5n105计算量约为1.7 × 10 6 1.7 \times 10^61.7×106次耗时仅几毫秒轻松 AC。空间复杂度O ( n ) \mathcal{O}(n)O(n)用于存储原数组及备份数组。