Gym-104354F-Art for Last (单调队列)
题意：n个数中选k个数出来，使得这些数的任意两个数相减得到的最小值与最大值的乘积最小
分析：遍历n个数排序后的连续k个数，维护两数之差的最大值和最小值即可。
首先，在排序以后，相邻的两个数相减是最小，其次，对于选择k个数，长度为k的两端做差一定是最小。
用单调队列维护原数组排序后做差的数组中长度为k的滑动窗口即可。
const int N = 5e5 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int a[N], b[N];
void solve() {
int n, k; cin >> n >> k;
for (int i = 1; i <= n; i++)cin >> a[i];
sort(a + 1, a + 1 + n);
for (int i = 1; i < n; i++)b[i] = a[i + 1] - a[i];
b[n] = 1e9;
ll ans = inf;
ll x = inf, y = -inf;
deque<int>q;
ll tmp = 0;
for (int i = 1; i <= n; i++) {
if (q.empty())q.push_back(i);
else {
while (!q.empty() && (q.back() - q.front() >= k - 1))q.pop_front();
while (!q.empty() && b[q.back()] > b[i])q.pop_back();
q.push_back(i);
}
if (i <= n - 1)tmp = a[i + 1] - a[i - k + 2];
else tmp = a[n] - a[i - k + 1];
if (i + 1 >= k && !q.empty())ans = min(ans, b[q.front()] * 1ll * tmp);
}
cout << ans << endl;
}