3229. 使数组等于目标数组所需的最少操作次数

Powered by:NEFU AB-IN

Link

3229. 使数组等于目标数组所需的最少操作次数

题意

给你两个长度相同的正整数数组 nums 和 target。

在一次操作中，你可以选择 nums 的任何
子数组
，并将该子数组内的每个元素的值增加或减少 1。

返回使 nums 数组变为 target 数组所需的 最少 操作次数。

思路

两种思路都要理解，思路二是最简便的
题型类似：
给你一个数组，可以每个元素的值增加或减少1，问多少次操作能变成目标数组

https://leetcode.cn/problems/minimum-operations-to-make-array-equal-to-target/solutions/2851722/chai-fen-shu-zu-fen-lei-tao-lun-pythonja-f8lo/

总体思路就是两个数组求差，这就是要刚才说的目标数组，然后对这个数组进行差分

1. 第一种思路是分类讨论，记录s为表示对 d[i] 增大/减少的累积量，大致思路就是，从前往后遍历差分数组，对d和s进行分类讨论。如果遇到d为正数，说明后面的值可以免费减少d次。
2. 第二种思路就是，比如目标数组为 a=[1,−2,2]，差分数组为 d=[1,−3,4,−2]，d[n]=(-2)=-a[n-1]，这个-2也就是垃圾堆，平常不显示。其实d数组的总和就是0，我们可以把差分数组中的正数和负数一一对应起来，每次操作会产生一个 +1 和一个 −1，所以操作次数就等于所有正数 d[i] 之和，或者负数之和的相反数。

和 https://leetcode.cn/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/description/
很像

代码

'''
Author: NEFU AB-IN
Date: 2024-07-23 17:13:58
FilePath: \LeetCode\3229\3229.py
LastEditTime: 2024-07-23 17:24:03
'''
# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Dict, List, Optional, Tuple, TypeVar, Union

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(int(2e9))


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class IO:
    input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
    read = staticmethod(lambda: map(int, IO.input().split()))
    read_list = staticmethod(lambda: list(IO.read()))


class Std:
    class Func:
        @staticmethod
        def pairwise(iterable):
            """Return successive overlapping pairs taken from the input iterable."""
            a, b = tee(iterable)
            next(b, None)
            return zip(a, b)

# ————————————————————— Division line ——————————————————————


class Solution:
    def minimumOperations(self, nums: List[int], target: List[int]) -> int:
        a = [0] + [t - x for x, t in zip(nums, target)] + [0]  # 前后加 0，方便计算
        return sum(max(y - x, 0) for x, y in Std.Func.pairwise(a))

原文地址：https://blog.csdn.net/qq_45859188/article/details/140701575

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！