题目描述：
给你一个长度为 n 下标从 0 开始的整数数组 nums 。
你可以对 nums 执行特殊操作 任意次 （也可以 0 次）。每一次特殊操作中，你需要 按顺序 执行以下步骤：
- 从范围
[0, n - 1] 里选择一个下标 i 和一个 正 整数 x 。 - 将
|nums[i] - x| 添加到总代价里。 - 将
nums[i] 变为 x 。
如果一个正整数正着读和反着读都相同，那么我们称这个数是 回文数 。比方说，121 ，2552 和 65756 都是回文数，但是 24 ，46 ，235 都不是回文数。
如果一个数组中的所有元素都等于一个整数 y ，且 y 是一个小于 109 的 回文数 ，那么我们称这个数组是一个 等数数组 。
请你返回一个整数，表示执行任意次特殊操作后使 nums 成为 等数数组 的 最小 总代价。
数据范围：
$1\le n \le 10^5$
题解：
假设最后全是 $x$ ，则就是假设所有的元素为 $x_i \le x \lt x_j$ 。也就是数组中左侧的元素全为 $x_i$ ，右侧的全为 $x_j$ ， $x$ 是一个分界线。
总代价就是 $\sum x - x_i + \sum x_j - x$ 。跟上面那个题目类似，当 $x$ 等于中位数时有最小值，但是增加了回文数限制，因此可以找中位数两侧最近的回文数，然后取最小值即可。
需要找一个数左右两侧的回文数，这个不是很好处理。
可以先预处理出所有的在 $[1,1e9]$ 范围内的回文数，可以先枚举左半边，然后翻转左半边，然后拼接得到。
而且需要写成预处理代码只会运行一遍的那种，减少运行时间。
先找中位数左侧最接近的回文数，比如找小于中位数的，可以使用lower_bound 找出来大于等于的，然后再减一。找小于等于的可以使用 upper_bound 然后减一。
再去找中位数右侧最接近的回文数，比如找大于等于的，可以使用lower_bound找出来大于等于的。找大于的可以直接 upper_bound。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
vector<int> a;
auto init = []()
{
for (int i = 0; i <= 10000; ++i)
{
long long num = i;
int tmp = i;
while (tmp)
{
num = num * 10 + tmp % 10;
tmp /= 10;
}
if (num >= 1 && num <= 1000000000)
a.emplace_back(num);
for (int j = 0; j < 10; ++j)
{
num = i * 10 + j;
tmp = i;
while (tmp)
{
num = num * 10 + tmp % 10;
tmp /= 10;
}
if (num >= 1 && num <= 1000000000)
a.emplace_back(num);
}
}
sort(a.begin(), a.end());
cout << a.back() << endl;
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
long long cost(vector<int> &nums, int x)
{
long long ret = 0;
for (auto &y : nums)
ret += abs(y - x);
return ret;
}
long long minimumCost(vector<int> &nums)
{
int n = nums.size();
sort(nums.begin(), nums.end());
int x = nums[n / 2];
long long sum = 0;
for (auto &x : nums)
sum += x;
long long ans = LLONG_MAX;
int index = lower_bound(a.begin(), a.end(), x) - 1 - a.begin();
if (index > 0)
ans = min(ans, cost(nums, a[index]));
index = lower_bound(a.begin(), a.end(), x) - a.begin();
if (index != a.size())
ans = min(ans, cost(nums, a[index]));
return ans;
}
};
|