LC 2967. 使数组成为等数数组的最小代价
https://leetcode.cn/problems/minimum-cost-to-make-array-equalindromic/
大概可以分解成为3个部分：
- 我们将数组排序的话，最优解肯定是在每个数的附近，但是我们怎么知道这些数的附近的“回文数”呢？
- 题目有个限制就是回文数的最大值是 10^9. 如果枚举前缀的话，这个量级差不多就是 10^5 (大概枚举出来是10999).
- 然后我们遍历回文数，期间会穿过 `nums`. 可以通过记录中间的状态变化，达到 `O(N)` 的时间复杂度。
题目还有两个优化：
- 回文数不用每次都计算。这个计算好像放在class init里面不行，还必须写在全局代码初始化里面。
- 可以根据 `nums` 最大最小值选择回文数，这个过程可以将许多回文数删除掉。
代码稍微有点乱，在 `cap_options` 里面还用了二分，不用二分时间会上来许多。
#!/usr/bin/env python
# coding:utf-8
# Copyright (C) dirlt
from typing import List
def gen_options(N):
def reverse(x):
ans = 0
while x:
ans = ans * 10 + x % 10
x = x // 10
return ans
for x in range(10):
yield x
for sz in range(2, N):
mid = sz // 2
lower, upper = 10 ** (mid - 1), 10 ** mid
if sz % 2 == 1:
for head in range(lower, upper):
tail = reverse(head)
for x in range(10):
yield (head * 10 + x) * upper + tail
else:
for head in range(lower, upper):
tail = reverse(head)
yield head * upper + tail
OPTIONS = list(gen_options(10))
class Solution:
def minimumCost(self, nums: List[int]) -> int:
nums.sort()
options = OPTIONS
def cap_options():
s, e = 0, len(options) - 1
while s <= e:
m = (s + e) // 2
if options[m] > nums[0]:
e = m - 1
else:
s = m + 1
lower = e
s, e = 0, len(options) - 1
while s <= e:
m = (s + e) // 2
if options[m] < nums[-1]:
s = m + 1
else:
e = m - 1
upper = s
return options[lower: upper + 1]
capped_options = cap_options()
acc = ans = sum(nums)
left, last = 0, 0
i = 0
for x in capped_options:
a, b = 0, 0
acc += left * (x - last)
while i < len(nums) and nums[i] <= x:
left += 1
a += abs(nums[i] - last)
b += abs(nums[i] - x)
i += 1
acc -= a
acc += b
right = len(nums) - left
acc -= right * (x - last)
last = x
ans = min(ans, acc)
# print(x, acc)
return ans