Gym-104354F-Art for Last

yxyxyxyxyx / 2023-09-05 / 原文

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;
}

题目链接：https://vjudge.net/problem/Gym-104354F/origin