登录
3495. 使数组元素都变为零的最少操作次数
解法
思路和算法
对正整数 $x$ 执行除以 $4$ 向下取整，将 $x$ 变成 $0$ 的执行次数与 $x$ 的值的关系如下：当 $1 \le x < 4$ 时，需要执行 $1$ 次；当 $4 \le x < 16$ 时，需要执行 $2$ 次；当 $16 \le x < 64$ 时，需要执行 $3$ 次；以此类推，当存在正整数 $p$ 满足 $4^{p - 1} \le x < 4^p$ 时，需要执行 $p$ 次。因此将 $x$ 变成 $0$ 的执行次数是 $\lfloor \log_4 x \rfloor + 1$。
对于二维数组 $\textit{queries}$ 中的每个查询 $[\textit{left}, \textit{right}]$，可以分别计算从 $\textit{left}$ 到 $\textit{right}$ 的每个正整数的执行次数，并得到区间 $[\textit{left}, \textit{right}]$ 中的所有正整数的执行次数之和。
由于 $\textit{left}$ 和 $\textit{right}$ 的取值范围是 $1 \le \textit{left} < \textit{right} \le 10^9$，因此如果直接遍历区间 $[\textit{left}, \textit{right}]$ 中的每个正整数计算执行次数，则时间复杂度过高，需要优化。
为了计算区间 $[\textit{left}, \textit{right}]$ 中的所有正整数的执行次数之和，可以分别计算区间 $[1, \textit{right}]$ 中的所有正整数的执行次数之和与区间 $[1, \textit{left} - 1]$ 中的所有正整数的执行次数之和，两项之差即为区间 $[\textit{left}, \textit{right}]$ 中的所有正整数的执行次数之和。
对于非负整数 $\textit{num}$，计算区间 $[1, \textit{num}]$ 中的所有正整数的执行次数之和的方法如下。
-
用 $\textit{currReductions}$ 表示当前执行次数，用 $\textit{start}$ 表示执行次数是 $\textit{currReductions}$ 的最小正整数，初始时 $\textit{currReductions} = 1$，$\textit{start} = 1$。
-
对于每个 $\textit{start}$ 计算 $\textit{end} = \min(\textit{start} \times 4 - 1, \textit{num})$，则区间 $[\textit{start}, \textit{end}]$ 为执行次数是 $\textit{currReductions}$ 的所有正整数的区间，该区间中的正整数个数是 $\textit{end} - \textit{start} + 1$，因此将区间 $[1, \textit{num}]$ 中的所有正整数的执行次数之和增加 $\textit{currReductions} \times (\textit{end} - \textit{start} + 1)$。然后将 $\textit{start}$ 的值乘以 $4$，将 $\textit{currReductions}$ 的值增加 $1$，重复上述操作。当 $\textit{start} > \textit{num}$ 时，结束操作，得到区间 $[1, \textit{num}]$ 中的所有正整数的执行次数之和。特别地，当 $\textit{num} = 0$ 时，上述做法也适用。
将区间 $[\textit{left}, \textit{right}]$ 中的所有正整数的执行次数之和记为 $\textit{reductions}$。当每次操作对两个正整数执行除以 $4$ 向下取整时，区间 $[\textit{left}, \textit{right}]$ 的最少操作次数等于 $\Big\lceil \dfrac{\textit{reductions}}{2} \Big\rceil$。理由如下。
-
对于正整数 $x$，用 $r(x)$ 表示对正整数 $x$ 执行除以 $4$ 向下取整，将 $x$ 变成 $0$ 的执行次数，则 $r(x) = \lfloor \log_4 x \rfloor + 1$。将区间 $[\textit{left}, \textit{right}]$ 中的每个正整数 $x$ 都替换成 $r(x)$，则得到从 $r(\textit{left})$ 到 $r(\textit{right})$ 的 $\textit{right} - \textit{left} + 1$ 个正整数组成的新数组，将新数组记为 $\textit{reductionsArr}$，则问题转换成：每次从新数组 $\textit{reductionsArr}$ 中选择两个元素分别减少 $1$，计算将新数组 $\textit{reductionsArr}$ 中的所有元素都变成零或负数的最少操作次数（由于 $0$ 除以 $4$ 仍等于 $0$，因此新数组中的元素变成负数也符合原数组中的元素变成 $0$）。
-
根据 $r(x)$ 的性质，新数组 $\textit{reductionsArr}$ 为单调递增数组且任意两个相邻元素之差等于 $0$ 或 $1$。每次从新数组 $\textit{reductionsArr}$ 中选择最大的两个元素分别减少 $1$，则可以经过若干次操作将所有的最大元素都减少 $1$ 且最多有一个次大元素减少 $1$。
-
经过若干次操作之后，一定可以将新数组 $\textit{reductionsArr}$ 变成所有元素值都相等（例如全部是 $r$）或其中一个元素值等于其余每个元素值加 $1$（例如只有一个元素是 $r + 1$，其余元素都是 $r$）。对于两种情况，都可以将元素值同步减少，直到所有元素变成 $0$ 或其中一个元素值是 $1$ 且其余每个元素值都是 $0$，当剩余一个元素值是 $1$ 时还需要额外操作一次才能将新数组 $\textit{reductionsArr}$ 中的所有元素都变成零或负数。因此在操作结束之后，新数组 $\textit{reductionsArr}$ 中最多有一个元素是 $-1$，其余元素都是 $0$，最少操作次数等于 $\Big\lceil \dfrac{\textit{reductions}}{2} \Big\rceil$。
分别计算二维数组 $\textit{queries}$ 中的每个查询的最少操作次数，计算所有查询结果的总和，即为答案。
代码
###Java
class Solution {
public long minOperations(int[][] queries) {
long operations = 0;
for (int[] query : queries) {
long reductions = countReductions(query[1]) - countReductions(query[0] - 1);
operations += (reductions + 1) / 2;
}
return operations;
}
public long countReductions(int num) {
long reductions = 0;
int currReductions = 1;
long start = 1;
while (start <= num) {
long end = Math.min(start * 4 - 1, num);
reductions += currReductions * (end - start + 1);
start *= 4;
currReductions++;
}
return reductions;
}
}
###C#
public class Solution {
public long MinOperations(int[][] queries) {
long operations = 0;
foreach (int[] query in queries) {
long reductions = CountReductions(query[1]) - CountReductions(query[0] - 1);
operations += (reductions + 1) / 2;
}
return operations;
}
public long CountReductions(int num) {
long reductions = 0;
int currReductions = 1;
long start = 1;
while (start <= num) {
long end = Math.Min(start * 4 - 1, num);
reductions += currReductions * (end - start + 1);
start *= 4;
currReductions++;
}
return reductions;
}
}
复杂度分析
-
时间复杂度：$O(n \log m)$，其中 $n$ 是数组 $\textit{queries}$ 的长度，$m$ 是数组 $\textit{queries}$ 中的最大值。需要计算 $n$ 个查询的结果，每个查询的计算时间是 $O(\log m)$，因此时间复杂度是 $O(n \log m)$。
-
空间复杂度：$O(1)$。
