题目描述

难度分:$1400$

输入$T(\leq 2 \times 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(2 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^8)$。

选择一个整数$x(0 \leq x \leq 10^9)$，生成一个序列$b$，满足$b[i]=|a[i]-x|$且$b[i] \leq b[i+1]$。

如果不存在这样的$x$，输出$-1$，否则输出任意一个符合要求的$x$。

输入样例

8
5
5 3 3 3 5
4
5 3 4 5
8
1 2 3 4 5 6 7 8
6
10 5 4 3 2 1
3
3 3 1
3
42 43 42
2
100000000 99999999
6
29613295 52036613 75100585 78027446 81409090 73215

输出样例

4
-1
0
42
2
-1
100000000
40741153

算法

分类讨论

只需要对于任意的$i \in [1,n]$都满足$|a[i]-x| \leq |a[i+1]-x|$即可。

1. 如果$a[i]=a[i+1]$，$x$随便取什么值都可以。
2. 如果$a[i] \lt a[i+1]$，把绝对值拆开进行分类讨论，可以得到$x \leq [\frac{a[i]+a[i+1]}{2}]$，其中$[.]$表示对$.$向下取整。
3. 如果$a[i] \gt a[i+1]$，把绝对值拆开进行分类讨论，可以得到$x \geq [\frac{a[i]+a[i+1]+1}{2}]$。

对于每个相邻的数对，维护$x$左边界$l$的最大值，以及$x$右边界$r$的最小值。如果最后$l \gt r$就无解，否则区间$[l,r]$中任何一个数都可以作为$x$。

复杂度分析

时间复杂度

只遍历了一遍数组$a$，时间复杂度为$O(n)$。

空间复杂度

除开输入的数组$a$，在整个算法过程中只使用了有限几个变量，额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 200010;
int t, n, a[N];

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        int r = 1e9, l = 0;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            if(i >= 2) {
                if(a[i - 1] < a[i]) {
                    r = min(r, (a[i - 1] + a[i])/2);
                }else if(a[i - 1] > a[i]) {
                    l = max(l, (a[i - 1] + a[i] + 1)/2);
                }
            }
        }
        if(l > r) puts("-1");
        else printf("%d\n", r);
    }
    return 0;
}