D-莲子的物理热力学
题目背景
莲子正在研究分子的运动。
每个分子都有一个速度，约定正方向为正，负方向为负。分子的数量极多，速度又并不一致，看上去杂乱无章。于是莲子希望调整部分分子的速度，使得最终分子们看上去整齐。
题目描述
莲子给定了 \(n\) 个整数 \(a_1,a_2,\cdots a_n\)，描述每个分子。现在她可以进行至多 \(m\) 次操作（也可以一次也不进行），每次操作可以执行以下两条之一：
- 选择 \(i\)，满足 \(a_i=\min_j\{a_j\}\)，然后将 \(a_i\) 变为 \(\max_j\{a_j\}\)。
- 选择 \(i\)，满足 \(a_i=\max_j\{a_j\}\)，然后将 \(a_i\) 变为 \(\min_j\{a_j\}\)。
现在莲子希望需要最小化最终序列的极差（最大值减去最小值的差）。请求出最小的极差。
例如，对于序列 \(a=\{5,1,4\}\)，可以进行如下几次操作：
- 选择 \(i=1\)，满足 \(a_1=5\) 是当前的最大值 \(5\)，可以将 \(a_1\) 修改成当前的最小值 \(1\)，此时序列变成 \(\{1,1,4\}\)；
- 再选 \(i=2\)，满足 \(a_2=1\) 是当前的最小值 \(1\)，可以将 \(a_2\) 修改成当前的最大值 \(4\)，此时序列变成 \(\{1,4,4\}\)。
这两次操作后得到的序列为 \(\{1,4,4\}\)。最大值减去最小值的差为 \(|4-1|=3\)。
当然，这种操作方式得到的极差并非最小。最优策略是，先将最大值 \(a_1=5\) 变成目前的最小值 \(1\)，再把此时的最大值 \(a_3=4\) 变成目前的最小值 \(1\)。此时序列为 \(\{1,1,1\}\)，得到的极差 \(|1-1|=0\) 是所有策略中最小的。
输入格式
- 第一行有两个正整数 \(n,m\)，分别表示序列的长度和你最多可以进行的操作次数。
- 第二行有 \(n\) 个整数 \(a\)，描述给定的序列。
输出格式
- 输出共一行一个整数，表示最优策略下能得到的最小极差。
样例 #1
样例输入 #1
样例输出 #1
样例 #2
样例输入 #2
样例输出 #2
样例 #3
样例输入 #3
样例输出 #3
提示
样例解释
样例 \(1\)：\(\{5,1,4\}\to\{1,1,4\}\to\{1,1,1\}\)，极差为 \(0\)。
样例 \(2\)：\(\{1,2,3,4,5,6,7,8\}\)，什么也做不了，极差为 \(7\)。
样例 \(3\)：\(\{1,5,5,5,6,6,9,10\}\to\{10,5,5,5,6,6,9,10\}\to\{5,5,5,5,6,6,9,10\}\to\{5,5,5,5,6,6,9,5\}\)，极差为 \(4\)。
数据范围及约定
对于全部数据，保证 \(1\le n \le 10^5\)，\(0\le m\le10^9\)，\(|a_i|\le 10^9\)。
思路：贪心
假设进行了 \(m\) 次操作之后的最优值域为：\([l, r]\)，则在原来 \(a\) 数组内所有严格小于 \(l\)，所有严格大于 \(r\) 的数都被操作了。
假设所有严格小于 \(l\) 的个数为 \(u\)，所有严格大于 \(r\) 的个数为 \(v\)，为了研究方便，我们先将原数组 \(a\) 从小到大的顺序排列，那么严格小于 \(l\) 的数据是排序后的数组左边前 \(1 \sim u\) 个数，严格大于 \(r\) 的数据是排序后的数组右边前 \(1 \sim v\) 个数。
我们先把左边前 \(1 \sim u\) 个数都转成最大值放到右边，则现在比 \(l\) 严格小的数为 0 个，比 \(r\) 严格大的数有 \(u + v\) 个，接着将 \(u + v\) 个数全部转成最小值放到最左边，则 比 \(l\) 小的数和比 \(r\) 大的数全部为 0 个，这里操作了：
\(u + u + v\) 次
如果一开始我是先将右边前 \(1 \sim v\) 个数放到最左边，按照上面的逻辑再放到最右边，这里操作了：
\(v + u + v\) 次
两种操作都能达到目的，我们要选择操作数最小的：
\(u + v + min(u, v)\)
我们要如何确定出 \(l\) 呢？
只能从左边一个一个遍历，不断的假定当前的节点就是 \(l\) 。
如果 \(l\) 固定为某个值，\(r\) 怎么求？假设 \(l - 1 \leq n - r\) ，则 \(u + v + min(u, v) \leq m\) 就可以变成：\(l - 1 + n - r + l - 1 = n + 2l - 2 - r \leq m\)，则 \(r \geq n + 2l - 2 - m\) 还得满足假设条件：\(l - 1 \leq n - r\) 所以:
\(n + 2l - 2 - m \leq r \leq n - l + 1\)，此时 \(3l - 3 \leq m\)
如果 \(l\) 固定为某个值，并假设 \(l - 1 \geq n - r\)，则 \(u + v + min(u, v) \leq m\) 就可以变成：\(l - 1 + n - r + n - r = 2n - 2l + l - 1 \leq m\) 还要满足假设条件：\(l - 1 \geq n - r\)，所以有：
\(2r \geq \max(2n - m + l - 1, 2n - 2l + 2)\)
由于上述两种假设相互对立，不是假设一成立，就是假设二成立，所以我们可以通过 \(3l - 3 \leq m\) 是否成立来选取那种对应的假设，如果成立，选取 \(n + 2l - 2 - m \leq r\)；否则选取 \(2r \geq \max(2n - m + l - 1, 2n - 2l + 2)\)，这里的 \(r\) 要向上取整，向上取整照样满足 \(l - 1 \geq n - r\) 这个条件。
当然 \(l\) 最多只能去到 \(m + 1\) ，\(r\) 最大也只能是 \(n\) 不能越界！
若 \(3l - 3 \leq m\)，则 \(n + 2l - 2 - m \leq n\)；否则 \(2n - m + l - 1 \leq 2n，2n - 2l + 2 \leq 2n\)，若 \(r\) 取值 各自范围的最小，都能保证 \(r \leq n\) ，请放心使用。
特判：
如果 \(m \geq n - 1\) 则把数组 \(a\) 全部变成相同的值，极差为 0 ，此时最小。
如果 \(m = 0\) ，则极差为 \(\max\{b\} - \min\{a\}\)。
代码参考
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define endl '\n'
#define pique priority_queue
#define oier \
ios_base::sync_with_stdio(false);\
cin.tie(nullptr); cout.tie(nullptr);
#define cf int t; cin >> t; while (t --)
#define upfor(i, l, r) for (i = (l); i <= (r); i ++)
#define downfor(i, l, r) for (i = (r); i >= (l); i --)
// #define int long long
typedef long long LL;
typedef long double LD;
//typedef __int128_t int128;
const int inf = ~(1 << 31); // 正无穷
const int ninf = (1 << 31); // 负无穷
const LL infll = ~(1ll << 63); // 正无穷
const LL ninfll = (1ll << 63); // 负无穷
const int N = int (1e7 + 10);
inline LL rll() { oier LL x; cin >> x; return x; }
inline int rint() { oier int x; cin >> x; return x; }
/* ==========================代码区========================== */
int n, m;
int q[N];
void qsort(int l, int r)
{
if (l >= r) return;
int x = q[(l + r) / 2];
int i = l - 1, j = r + 1;
while (i < j)
{
while (q[++i] < x);
while (x < q[--j]);
if (i < j) swap(q[i], q[j]);
}
qsort(l, j); qsort(j + 1, r);
}
void solve()
{ oier
/* =========================== */
n = rint(); m = rint();
for (int i = 1; i <= n; i ++) q[i] = rint();
if (m >= n - 1) { cout << 0 << endl; return; }
int res = inf; qsort(1, n);
if (m == 0) { cout << q[n] - q[1] << endl; return; }
for (int l = 1, r; l <= m + 1; l ++)
{
if (3 * l - 3 <= m) r = n + 2 * l - 2 - m;
else r = max(2 * n - m + l - 1, 2 * n - 2 * l + 2) / 2.0 + 0.5;
res = min(res, q[r] - q[l]);
}
cout << res << endl;
/* =========================== */
}
/* ==========================代码区========================== */
/**
* _ooOoo_
* o8888888o
* 88" . "88
* (| -_- |)
* O\ = /O
* ____/`---'\____
* .' \\| |// `.
* / \\||| : |||// \
* / _||||| -:- |||||- \
* | | \\\ - /// | |
* | \_| ''\---/'' | |
* \ .-\__ `-` ___/-. /
* ___`. .' /--.--\ `. . __
* ."" '< `.___\_<|>_/___.' >'"".
* | | : `- \`.;`\ _ /`;.`/ - ` : | |
* \ \ `-. \_ __\ /__ _/ .-` / /
* ======`-.____`-.___\_____/___.-`____.-'======
* `=---='
* ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
* 佛祖保佑 永无BUG
* 佛曰:
* 写字楼里写字间，写字间里程序员；
* 程序人员写程序，又拿程序换酒钱。
* 酒醒只在网上坐，酒醉还来网下眠；
* 酒醉酒醒日复日，网上网下年复年。
* 但愿老死电脑间，不愿鞠躬老板前；
* 奔驰宝马贵者趣，公交自行程序员。
* 别人笑我忒疯癫，我笑自己命太贱；
* 不见满街漂亮妹，哪个归得程序员？
*/
int main()
{
// oier cf solve(); return 0;
oier solve(); return 0;
}