摘要
Title: 1674. 使数组互补的最少操作次数
Categories: 差分

1674. 使数组互补的最少操作次数

题意

给你一个长度为偶数 n 的整数数组 nums 和一个整数 limit 。每一次操作，你可以将 nums 中的任何整数替换为 1 到 limit 之间的另一个整数。

如果对于所有下标 i（下标从 0 开始），nums[i] + nums[n - 1 - i] 都等于同一个数，则数组 nums 是互补的。例如，数组 [1,2,3,4] 是互补的，因为对于所有下标 i ，nums[i] + nums[n - 1 - i] = 5 。

返回使数组互补的最少操作次数。

思路

https://leetcode.cn/problems/minimum-moves-to-make-array-complementary/solutions/504286/chai-fen-shu-zu-wei-he-chai-fen-ru-he-chai-fen-by-/

先了解最基本的移动次数的贡献
然后我们可以发现，当我们遇到一对数 (nums[i], nums[n - i - 1]) 的时候，target选择不同值时，会有不同的操作结果
所以，我们可以把所有的target值，抽象为一个数组，类似坐标系，当 (nums[i], nums[n - i - 1]) 满足某个情况时，将该范围的target都加上操作结果，这时候就可以用差分进行区间更新，最后遍历查询哪个target的操作值最小

代码

'''
Author: NEFU AB-IN
Date: 2024-07-23 16:18:08
FilePath: \LeetCode\1674\1674.py
LastEditTime: 2024-07-23 16:25:08
'''
# 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:
    pass

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


class Solution:
    def minMoves(self, nums: List[int], limit: int) -> int:
        n = len(nums)
        dis = Arr.array(0, 2 * limit + 3)
        for i in range(n // 2):
            a = Math.min(nums[i], nums[n - i - 1])
            b = Math.max(nums[i], nums[n - i - 1])

            # 1. target ∈ [2, a+1)，需要操作两次
            dis[2] += 2
            dis[a + 1] -= 2

            # 2. target ∈ [a+1, a+b)，需要操作一次
            dis[a + 1] += 1
            dis[a + b] -= 1

            # 3. target ∈ (a+b, b + limit]，需要操作一次
            dis[a + b + 1] += 1
            dis[b + limit + 1] -= 1

            # 4. target ∈ (b+limit, 2*limit]，需要操作两次
            dis[b + limit + 1] += 2
            dis[2 * limit + 1] -= 2

        sum_ = 0
        res = INF
        for i in range(2, 2 * limit + 1):
            sum_ += dis[i]
            res = Math.min(res, sum_)
        return res