3495. Minimum Operations to Make Array Elements Zero
思路:
从题目可以知道1个数字x要变成0需要花的次数
是取决于floor(log4(x)) + 1
假设位于 4^n ~ 4^(n+1) -1间的数字有i个
那需要花费的次数就为(n+1) * i
接着照上面的方法计算出每个query所需要的总次数 step
因为每次可以选两个数次出来/4
所以要将step / 2, 如果是奇数还要再 + 1
最后算完所有query就可以得到答案了
golang code :
func minOperations(queries [][]int) int64 {
ans := 0
interval := make([][2]int, 0, 31)
for i := 0; i < 31; i++ {
interval = append(interval, [2]int{1 << (2 * i), 1<<(2*(i+1)) - 1})
}
for _, query := range queries {
n := int(log4(float64(query[1])))
l, r := -1, -1
s := 0
for l != query[0] {
l, r = max(interval[n][0], query[0]), min(interval[n][1], query[1])
num := (r - l + 1)
s += num * (n + 1)
n