【Leetcode Daily】2602使数组元素全部相等的最少操作次数

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给两个数组，现在规定一次操作为对数组一的任意元素进行加一或者减一，对数组二的每个元素，求将数组一的全部数字经多次操作后，全部变成该元素的操作次数。

思路分享

• 有关距离和的基本思路，可以查看 【Leetcode Daily】1685有序数组中差绝对值之和

• 本题与此前的距离和模板题有一点不同，由于不确定要对哪个下标的数字做距离和，需要二分查找找到下标再开始求解，python 中可以通过 bisect 函数来快速找到下标（bisect_left 是求最左，而 bisect_right 求最右）。

  https://leetcode.cn/problems/minimum-operations-to-make-all-array-elements-equal/solutions/2191417/yi-tu-miao-dong-pai-xu-qian-zhui-he-er-f-nf55/

• 由于本题的操作不涉及原始序列，可以排序后再进行操作，这样才能用距离和。如果不能确保单调性，应该是得换个方法的。

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:
        
        nums.sort()
        s = list(accumulate(nums, initial=0))
        n = len(nums)
        ans = []
        for i in queries:
            index = bisect_left(nums, i)
            left = index*i - s[index] 
            right = s[n] - s[index] - (n-index)*i
            ans.append(left+right)
        return ans