洛谷P8872 莲子的物理热力学

你可以在一次操作中将一个数变为全局最大值或最小值，问n个给定的数在m次操作后最小的极差是多少

考虑将n个数排序，假设 \(m\) 次操作后，剩下来的数字的值域为 \([l,r]\)，那么所有小于 \(l\) 的数字和大于 \(r\) 的数字肯定被操作了，于是考虑枚举 \(l\) 和 \(r\)，考虑我们删掉的数越多一定不会更劣，那么我们可以枚举 \(l\) 和 \(r\) 中的一个即可

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout);
#define dbg(x) cerr<<"In Line"<<__LINE__<<" the "<<#x<<" = "<<x<<'\n';
#define abs(x) ((x) < 0 ? -(x) : (x))

using namespace std;

const int N = 2e6 + 10;

const long long INF = 1ll << 40;

inline int read() {
	bool sym = 0; int res = 0; char ch = getchar();
	while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
	return sym ? -res : res;
}

int n, m, k, a[N];

int main() {
	n = read(); m = read();
	for (int i = 1; i <= n; i++) a[i] = read();
	if (m >= n - 1) {printf("0\n"); return 0;}
	sort(a + 1, a + n + 1); long long ans = INF;
	for (int i = 0; i <= m / 2; i++) {
		ans = min(ans, 1ll * a[n - m + i * 2] - a[i + 1]);
	}
	for (int i = 0; i <= m / 2; i++) {
		ans = min(ans, 1ll * a[n - i] - a[m - i * 2 + 1]);
	}
	printf("%lld\n", ans);
	return 0;
}