Description

给定一个长度为 \(n\) 的序列，你可以选取一个长度为 \(m\) 的元素在原序列中不相邻的子序列，使得该子序列极差最小。

对于所有数据，\(1\leq n,m\leq 10^5\)。

Solution

先将序列从小到大排序，考虑枚举被选取子序列中的最小值 \(L\) 与最大值 \(R\)。将序列中大于等于 \(L\) 且小于等于 \(R\) 的数标记，则会形成若干个被标记的连续段。一个长为 \(k\) 的连续段可以选出 \(\lceil\dfrac{k}{2}\rceil\) 个数，若能选出的数的总和 \(\geq m\) 则这种选择合法。

在 \(L\) 变大的同时 \(R\) 也会变大，考虑双指针。用 set 维护数的加入与删除即可。

时间复杂度 \(\mathcal{O}(n\log m)\)。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
namespace Cadmus {
    typedef long long LL;
    typedef pair<LL, LL> pii;
    typedef set<pii>::iterator IT;
    const int N = 1e6 + 5;
    LL n, m, now, ans; pii a[N];
    set<pii> s;
    LL calc(IT t) { return (t->se - t->fi + 2) / 2; }
    void insert(LL x) {
        if (s.empty()) { s.insert(pii(x, x)), now ++; return; }
		IT itr = s.upper_bound(pii(x, 0)), itl;
        int l = x, r = x;
        if (itr != s.begin()) itl = prev(itr);
        if (itr != s.begin() && itl->se == x - 1)
            now -= calc(itl), l = itl->fi, s.erase(itl);
        if (itr != s.end() && itr->fi == x + 1)
            now -= calc(itr), r = itr->se, s.erase(itr);
        now += (r - l + 2) / 2, s.insert(pii(l, r));
    }
    void split(LL x) {
        IT it = s.upper_bound(pii(x, 0));
        if (it == s.end() || !(it->fi <= x && x <= it->se)) it --;
        int l = it->fi, r = it->se;
        now -= calc(it), s.erase(it);
        if (l < x) now += (x - l + 1) / 2, s.insert(pii(l, x - 1));
        if (r > x) now += (r - x + 1) / 2, s.insert(pii(x + 1, r));
    }
    int main() {
        cin >> n >> m, ans = INT_MAX;
        for (int i = 1; i <= n; i ++)
            cin >> a[i].fi, a[i].se = i;
        sort(a + 1, a + 1 + n);
        for (int l = 1, r = 0; l <= n; split(a[l].se), l ++) {
            while (r < n && now < m) insert(a[++ r].se);
            if (now >= m) ans = min(ans, a[r].fi - a[l].fi);
        }
        cout << ans << '\n';
        return 0;
    }
}
int main() {
    int T = 1;
    while (T --) Cadmus::main();
    return 0;
}