398小L的元素修改问题

题目描述

小 R 拿到了一个数组，她可以进行如下操作：使得一个元素加1，另一个元素减1。她希望最终数组的每个元素大小都在$ [l, r] $的范围内。小 R 想知道，最少需要多少次操作可以达到目标。

如果无法通过有限次操作使所有元素都落在指定范围内，则返回 -1。

解题思路

为了使数组中的所有元素都落在区间 ([l, r]) 内，小 R 可以通过进行以下操作来调整数组：

1. 统计调整需求：

   • 遍历数组，计算所有小于 (l) 的元素需要增加的总次数（记为 cnt1）。
   • 计算所有大于 (r) 的元素需要减少的总次数（记为 cnt2）。

2. 验证总和条件：

   • 计算数组元素的总和 (s)。

   • 检查是否满足 (l \times n \leq s \leq r \times n)。

     • 如果不满足，说明无法通过有限次操作将所有元素调整到指定范围内，返回 -1。

   • 如果满足总和条件，所需的最小操作次数为 cnt1 和 cnt2 中的较大值。这是因为每一次操作可以同时满足一个增加和一个减少的需求。

代码实现

def solution(n: int, l: int, r: int, a: list) -> int:
    cnt1 = cnt2 = s = 0
    for x in a:
        if x < l:
            cnt1 += l - x
        if x > r:
            cnt2 += x - r
        s += x
    return max(cnt1, cnt2) if l * n <= s <= r * n else -1


if __name__ == '__main__':
    print(solution(n = 2, l = 3, r = 5, a = [1, 2]) == -1)
    print(solution(n = 3, l = 4, r = 6, a = [3, 6, 5]) == 1)
    print(solution(n = 4, l = 2, r = 8, a = [1, 10, 2, 6]) == 2)

复杂度分析

时间复杂度：$O(n)$，其中$ n $是数组的长度。
空间复杂度：$O(1)$。