Absolute Sorting

题意

给定一个乱序数组，判断是否存在一个数值x，让这个数组减去x后非递减排序。并且$a[i] = abs(a[i] - x)$。如果存在，输出x，否则输出-1。

⭐rating: 1400

分析

如果 $a_i=a_{i+1}$，始终存在 $|a_i-x|\le|a_{i+1}-x|$ 的情况，对于任意的 $x$ 都可以取到。

对于 $a_i\le a_{i+1}$ 的情况：

$x\le a_i$ 时： $$ \begin{aligned} |a_i-x|\le|a_{i+1}-x| & \rightarrow a_i\le a_{i+1} \end{aligned} $$
$a_i\le x\le a_{i+1}$ 时：

\[\begin{aligned} |a_i-x|\le|a_{i+1}-x| & \rightarrow 2x\le a_i+a_{i+1} \\ & \rightarrow x\le \left \lfloor \frac{a_i+a_{i+1}}{2} \right \rfloor \\ \end{aligned}\]

$a_{i+1}\le x$ 时：

\[\begin{aligned} |a_i-x|\le|a_{i+1}-x| & \rightarrow a_{i+1}\le a_i \end{aligned}\]

上述可得，$x\le \left \lfloor \frac{a_i+a_{i+1}}{2} \right \rfloor$ 时满足 $a_i\le a_{i+1}$ 的条件。

同理可以推出，当 $a_{i+1}\le a_{i}$ 时，需要满足 $x\ge \left \lceil \frac{a_i+a_{i+1}}{2} \right \rceil$ 的条件。

如果存在一个 $x$ 可以满足使最后的序列 sorted，那么必然满足 $x$ 大于最大的下界且小于最小的上界。

代码

GoC++

package main

import ("bufio";."fmt"; "os")

func max(a, b int) int {
    if (a < b) {
        return b
    }
    return a
}

func min(a, b int) int {
    if (a > b) {
        return b
    }
    return a
}

func main() {
    in := bufio.NewReader(os.Stdin)
    var T int
    Fscan(in, &T)
    for ; T > 0; T-- {
        var n int
        Fscan(in, &n)
        p := make([]int, n)
        for i := range p {
            Fscan(in, &p[i])
        }

        mx := int(1e9)
        mn := 0
        for i := 1; i < n; i++ {
            if (p[i] > p[i - 1]) {
                mx = min(mx, (p[i] + p[i - 1]) / 2)
            } else if (p[i] < p[i - 1]) {
                mn = max(mn, (p[i] + p[i - 1] + 1) / 2)
            }
        }

        if (mn <= mx) {
            Println(mn)
        } else {
            Println(-1)
        }
    }
}

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int &x : p) cin >> x;

    int mx = int(1e9), mn = 0;
    for (int i = 1; i < n; i++) {
        if (p[i] == p[i - 1]) continue;
        else if (p[i] > p[i - 1]) mx = min(mx, (p[i] + p[i - 1]) / 2);
        else mn = max(mn, (p[i] + p[i - 1] + 1) / 2);
    }

    if (mn <= mx) cout << mn << endl;
    else cout << -1 << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}