ZYF064 数组的最小偏移量
大约 4 分钟
ZYF064 数组的最小偏移量
【算法】 贪心、优先队列(堆)
【C++】 priority_queue、vector
【难度】 普及+/提高
一、题目简述
给定 个正整数,可以进行任意次操作:
- 若元素为偶数,可除以
- 若元素为奇数,可乘
「偏移量」定义为 。求经过任意次操作后,数组的最小偏移量。
| 变量 | 范围 |
|---|---|
二、解题思路
2.1 梳理可到达的值
先分析每个数通过操作能变成哪些值:
偶数 :只能不断除以 ,直到变为奇数为止。例如 (奇数,停)。所以偶数只能在 中取值(最后一个为奇数)。
奇数 :只能乘以 ,变为 (偶数)。然后可以除以 变回 。所以奇数只能在 中取值。
💡 关键观察:每个数都只能往小了变(除了奇数可以翻一倍),且变化是单向的。操作无法让值任意增大,整体趋势是向下。
2.2 贪心策略
既然趋势向下,我们采用这样的策略:
- 先把所有奇数 ,让每个数都处于它能取到的最大值
- 此时所有数都是偶数(或已最大化),接下来只能除以 (只能减小)
- 每次挑选当前的最大值,将其除以 (缩小区间上界)
- 重复直到最大值变为奇数(无法再缩小上界)
为什么这样是对的? 初始所有数都取到最大,区间最宽。我们不断"压低天花板",每一步都试图缩小偏移量。由于每个数只能变小、不能变大,压低最大值是最直接的缩小区间方式。所有可能的"最优状态"都会在这个过程中被遍历到。
2.3 手动模拟
以样例 2:
第一步:奇数 →
| 步骤 | 当前堆(大根堆顶) | 当前最小值 | 偏移量 |
|---|---|---|---|
| 初始 | 20 | 2 | |
| 20÷2=10 | 10, 10, 6, 4, 2 | 2 | |
| 10÷2=5 | 10, 6, 5, 4, 2 | 2 | |
| 10÷2=5 | 6, 5, 5, 4, 2 | 2 | |
| 6÷2=3 | 5, 5, 4, 3, 2 | 2 | |
| 堆顶 5 为奇数 | 停止 | — | 答案 3 |
对应方案:,偏移量 。
2.4 算法步骤
- 读入数组,若 为奇数则
- 将所有数放入大根堆,记录当前最小值
curMin ans = 堆顶 - curMin- 循环:当堆顶为偶数时
- 弹出堆顶,除以 ,重新入堆
- 更新
curMin = min(curMin, 新值) - 更新
ans = min(ans, 堆顶 - curMin)
- 输出
ans
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
priority_queue<int> pq; // 大根堆
int curMin = INT_MAX; // 当前所有数的最小值
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (x % 2 == 1) x *= 2; // 奇数最大化
pq.push(x);
curMin = min(curMin, x);
}
int ans = pq.top() - curMin;
// 不断压低最大值
while (pq.top() % 2 == 0) {
int cur = pq.top();
pq.pop();
cur /= 2;
pq.push(cur);
curMin = min(curMin, cur);
ans = min(ans, pq.top() - curMin);
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:,其中 是元素最大值。每个数最多被除以 约 次,每次堆操作 。总操作次数约 ,可通过。
- 空间复杂度:,优先队列存储所有元素。
五、知识扩展
5.1 为什么奇数只乘一次?
奇数 (偶数)(除以 回到奇数),乘两次只会回到原点。所以奇数的值仅在 之间。相比之下,偶数的下降空间更大——这也是为什么初始要把奇数最大化:让所有数先"站到同一起跑线"(偶数),然后再统一向下调整。
5.2 为什么堆顶是奇数就停了?
此时堆顶(最大值)是奇数,不能除以 。若再乘以 ,只会让最大值变大,偏移量不可能减小。最小值同理,若最小值是偶数,除以 会让最小值更小,偏移量可能变大。所以一旦最大值无法下降,算法结束。
5.3 易错点
- 只操作最大值:每次都处理当前最大值,不要试图去动最小值——压低上界才是缩小区间的关键。
- 及时更新最小值:每次除以 后都可能诞生新的最小值。
- 停止条件:堆顶为奇数时停止,而不是堆为空。
5.4 类似题目
- LeetCode 1675. Minimize Deviation in Array —— 本题原题
- LeetCode 632. 最小区间 —— 类似的"压低边界"贪心思路
