【CF1772D】Absolute Sorting（数学，不等式）

【题目描述】
给定一个长度为$n$的正整数序列$a$，请你选择一个整数x(0≤x≤109)x(0\\le x\\le 10^9)x(0≤x≤109)，将所有的aia_iai​变为∣x−ai∣|x-a_i|∣x−ai​∣，使其满足：a1≤a2≤⋯≤ana_1\\le a_2\\le \\dots \\le a_na1​≤a2​≤⋯≤an​。如果存在多个解请任意输出一个，如果无解请输出$-1$。

【输入格式】
第一行一个整数t(1≤t≤2×104)t(1\\le t\\le 2\\times 10^4)t(1≤t≤2×104)，表示测试样例的数量。
对于每组测试样例第一行输入一个整数n(2≤n≤2×105)n(2\\le n\\le 2\\times 10^5)n(2≤n≤2×105)。
第二行输入$n$个整数a1,a2,…,an(1≤ai≤108)a_1,a_2,\\dots ,a_n(1\\le a_i\\le 10^8)a1​,a2​,…,an​(1≤ai​≤108)。
数据保证每组测试用例中的$n$的和不超过2×1052\\times 10^52×105。

【输出格式】
对于每组测试用例，输出一行共一个整数$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

【说明/提示】
In the first test case, after using $x=4$, the array becomes $[1,1,1,1,1]$.
In the third test case, after using $x=0$, the array becomes $[1,2,3,4,5,6,7,8]$.
In the fourth test case, after using $x=42$, the array becomes $[32,37,38,39,40,41]$.

【分析】

对于任意的$i$，操作后的序列满足ai≤ai+1a_i\\le a_{i+1}ai​≤ai+1​，因此只需要比较相邻元素即可，我们分以下几种情况讨论：

• ai=ai+1a_i=a_{i+1}ai​=ai+1​时，$x$取任何值在操作完后都满足ai≤ai+1a_i\\le a_{i+1}ai​≤ai+1​，即$x$的取值范围为$0\le x<+\infty$。
• ai<ai+1a_i<a_{i+1}ai​<ai+1​时，若要满足∣ai−x∣≤∣ai+1−x∣|a_i-x|\\le |a_{i+1}-x|∣ai​−x∣≤∣ai+1​−x∣，则$x$的取值范围为0≤x≤⌊ai+ai+12⌋0\\le x\\le \\lfloor \\frac{a_i+a_{i+1}}{2} \\rfloor0≤x≤⌊2ai​+ai+1​​⌋。
• ai>ai+1a_i>a_{i+1}ai​>ai+1​时，若要满足∣ai−x∣≤∣ai+1−x∣|a_i-x|\\le |a_{i+1}-x|∣ai​−x∣≤∣ai+1​−x∣，则$x$的取值范围为⌈ai+ai+12⌉≤x<+∞\\lceil \\frac{a_i+a_{i+1}}{2} \\rceil\\le x<+\\infin⌈2ai​+ai+1​​⌉≤x<+∞。

因此我们可以遍历所有相邻元素，求出$x$的所有取值范围，如果有公共部分则输出任意一个数即可，否则无解。

【代码】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;const int N = 200010;
int a[N];
int n;int main()
{int T;cin >> T;while (T--){cin >> n;for (int i = 0; i < n; i++) cin >> a[i];int l = 0, r = 1e8;for (int i = 0; i < n - 1; i++)if (a[i] < a[i + 1]) r = min(r, (int)floor(((double)a[i] + a[i + 1]) / 2));else if (a[i] > a[i + 1]) l = max(l, (int)ceil(((double)a[i] + a[i + 1]) / 2));if (l > r) cout << -1 << endl;else cout << l << endl;}return 0;
}