对于数组$a_1 - a_n$, 将其排序。
题中的两种操作分别是将最小的元素变成最大的元素、将最大的元素变成最小的元素。
不妨为每一个元素设一个数量状态, 初始时每一个元素的数量都为1.
而两种操作就是数量的转移, 如将a1变为an的过程就是$[a_1(1), a_2(1), …, a_n(1)] -> [a_2(1), a_3(1)...., a_n(2)]$, 通过了一次操作将$[a_1, a_n]$变成了$[a_2, a_n]$
考虑对于任意一段区间$[a_l, a_r]$, 将$[a_1, a_n]$变换为它的最小操作次数。
设$a_l左边的元素个数为x = l - 1, a_r右边的元素个数为y = n - r.$
结论是最小操作次数$z = x + y + min(x , y)$。
即 :假设x < y.
- 首先将$a_l$左边的元素都变为$a_n$, 操作了x次
- 此时$a_r$右边有x + y个元素, 将它们都变为此时的最小值$a_l$, 操作了x + y次
对于每一个元素$a_i$, 我们求出以它为左边界, 最短的且最小操作次数不大于m的区间, 因为在$a_i$确定为左边界的情况下, $a_j - a_i <= a_{j +1} - a_i$, 所以较短的区间的值域不会大于较长区间的值域. 在所有这样的区间中找到最小的值域。
而确定最小右边界这个过程可以用双指针优化。
#include <bits/stdc++.h>
using namespace std;
int main () {
int n, m; cin >> n >> m;
vector<int> a(n);
for (auto& x : a) cin >> x;
sort(a.begin(), a.end());
int res = 2e9;
for (int i = 0, j = 0; i < n && i <= m; i ++) {
if (j < i) j = i;
while (j + 1 < n && i + n - j - 1 + min(i, n - j - 1) > m) j ++;
res = min(res, a[j] - a[i]);
}
cout << res << endl;
return 0;
}
z=x+y+min(x+y) ,应该是min(x,y)
lz能解释下,最小操作次数为什么不是2x+y,而是x+y+min(x+y)吗
如果y比x小的话, 把$a_r$右边的先变成$a_1$, 总的操作次数就是2y + x, 比2x + y更小
懂了,谢谢