int的最大值是$2^{31} - 1 = 2147483647$

懵逼的 题目

某蛇皮的hihocoder

扯淡的 题解

我们惊喜的发现这个什么校验值就是把最大值和最小值配对, 次大值和次小值配对…

然后问题就变成了 给一个左端点, 找一个尽量靠右的右端点, 保证排序后配对的校验值小于$k$

右端点的扩大我们发现不必一次扩大一个, 而是可以倍增:

  • 设扩大步数为$p$, 初始化为$p = 1$, 当前区间内$[le, ri]$有一个数
  • ri += p 并检验加入区间后区间$[le, ri]$是否满足要求
    • 满足: $p = 2p$
    • 否则: $p = \frac{1}{2}p$, 并恢复ri的值
  • 直到$p = 0$, 当前区间无法扩展, 答案加一

还是挺有意思的?

沙茶的 代码

参照了LYD大爷的写法

调了一下午发现是$k = 10^{18}$爆了int

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAXN (500000 + 5)
#define LL long long
using namespace std;
int n, m, a[MAXN];
LL k;
bool cal(int xn, int* xa)
{
    LL re = 0;
    for (int i = 1; i <= min(xn >> 1, m); i++)
    {
        re += (LL)(xa[i] - xa[xn - i + 1]) * (xa[i] - xa[xn - i + 1]);
        if (re > k)
            return false;
    }
    return true;
}
void solve()
{
    int le = 0, ri = 0, ans = 0;
    while (ri < n)
    {
        ++ans;
        le = ri = ri + 1;
        int p = 1, dqa[MAXN], b[MAXN], c[MAXN], wza;
        dqa[dqa[0] = 1] = a[le];
        while (p)
        {
            if (ri + p > n)
            {
                p >>= 1;
                continue;
            }
            for (int i = 1; i <= p; i++)
                b[i] = a[ri + i];
            sort(b + 1, b + p + 1);
            b[0] = wza = 1, c[0] = 0;
            while (b[0] <= p && wza <= dqa[0])
                if (b[b[0]] < dqa[wza])
                    c[++c[0]] = b[b[0]++];
                else
                    c[++c[0]] = dqa[wza++];
            while (b[0] <= p)    c[++c[0]] = b[b[0]++];
            while (wza <= dqa[0])    c[++c[0]] = dqa[wza++];
            if (cal(c[0], c))
            {
                for (int i = 0; i <= c[0]; i++)    dqa[i] = c[i];
                ri += p;
                p <<= 1;
            }
            else
                p >>= 1;
        }
    }
    printf("%d\n", ans);
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d%lld", &n, &m, &k);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        solve();
    }
    return 0;
}

By 脑残 Cansult