[每日 B] Kevin and Geometry

前言

想着能做的题也不多, 直接当每日一练的形式写就好了

心态放平, 冷静利用时间

思路

转化题意

考虑一个等腰梯形的性质

朴素的想法是, 枚举 \(b\) , 枚举 \(c < b\) , 然后计算是否有对应的 \(a\) 满足 \(\exists a, \exists a + 2c\) , 特判 \(c = 0\)

这样直接爆炸, 考虑优化

考虑预处理出每个数作为 \(c\) 时的合法性, 也就是差值为 \(2c\) 的存在性问题
发现可以用差分数组的前后缀 \(\min\) 解决

具体一点, 如果存在 \(a + 2c - a < 2b\) 即可满足要求
考虑枚举 \(b\) , 然后判断是否存在差值 \(2c\) , 满足 \(c < b\)

需要注意的是跨过了两个 \(b\) 的处理, 即前后缀合并

实现

#include <bits/stdc++.h>
#define int long long
const int MAXN = 2e5 + 20;

int n;
int val[MAXN];
int dif[MAXN], pre[MAXN], suf[MAXN];


signed main()
{
    int t; scanf("%lld", &t);
    while (t--) {
        scanf("%lld", &n);
        for (int i = 1; i <= n; i++) scanf("%lld", &val[i]); std::sort(val + 1, val + n + 1);
        for (int i = 1; i < n; i++) dif[i] = val[i + 1] - val[i], pre[i] = suf[i] = 0;
        pre[0] = 0x3f3f3f3f; for (int i = 1; i < n; i++) pre[i] = std::min(pre[i - 1], dif[i]);
        suf[n] = 0x3f3f3f3f; for (int i = n - 1; i >= 1; i--) suf[i] = std::min(suf[i + 1], dif[i]);
        bool flag = false;
        for (int i = 1; i < n; i++) {
            if (val[i] != val[i + 1] || flag) continue;
            /*判断前缀*/
            if (i > 2) {
                /*出现答案*/
                if (pre[i - 2] < val[i] * 2) {
                    flag = true;
                    for (int j = 1; j < i - 1; j++) if (dif[j] == pre[i - 2]) { printf("%lld %lld %lld %lld\n", val[i], val[i + 1], val[j], val[j + 1]); break; }
                }
            }
            if (flag) continue;
            /*判断后缀*/
            if (i < n - 2) {
                /*出现答案*/
                if (suf[i + 2] < val[i] * 2) {
                    flag = true;
                    for (int j = i + 2; j < n; j++) if (dif[j] == suf[i + 2]) { printf("%lld %lld %lld %lld\n", val[i], val[i + 1], val[j], val[j + 1]); break; }
                }
            }
            if (flag) continue;
            /*判断前后缀*/
            if (i > 1 && i < n - 1) {
                if (val[i + 2] - val[i - 1] < val[i] * 2) {
                    flag = true;
                    printf("%lld %lld %lld %lld\n", val[i], val[i + 1], val[i - 1], val[i + 2]); break;
                }
            }
        }
        if (!flag) printf("-1\n");
    }

    return 0;
}

总结

常见的求差值存在性问题的方法, 可以转化成差分数组的形式
本质上是利用了最小的存在差值必定从相邻两项的差中产生

注意转化问题的方式
常见的类似前后缀的判断方式