# CF 1772 D. Absolute Sorting

:::info
[Link](https://codeforces.com/contest/1772/problem/D)
:::

:::spoiler 目錄
[toc]
:::

## 題意

給定一個有$n$個數的數列$a$，請找出一個$x$，使數列$b=[\forall i\in a, \vert i-x\vert]$為一個升序排序的數列。

## 官解

### 思路

對於數列$a$，升序表示$a_1\le a_2\le\cdots \le a_n$，現在假設經過題目的操作後，$x$可以讓$a$被升序排序。

由此可知我們的目標是使關係式$\vert a_i-x\vert\le\vert a_{i+1}-x\vert$成立，這時因為絕對值很難處理，所以要分case解決。
因此將$a_i$和$a_{i+1}$的關係分成以下三種：

1. $a_i=a_{i+1}$
$\vert a_i-x\vert\le\vert a_{i+1}-x\vert\\\Rightarrow \vert a_i-x\vert\le\vert a_i-x\vert$
可以看出$x$不管是多少該式都會成立
2. $a_i<a_{i+1}$
$\vert a_i-x\vert\le\vert a_{i+1}-x\vert$
可以分開考慮$x$的三種範圍是否滿足關係式
1. $x\le a_i$
$$
\vert a_i-x\vert\le\vert a_{i+1}-x\vert\\
\Rightarrow a_i - x\le a_{i+1} - x\\
\Rightarrow a_i\le a_{i + 1}
$$
此範圍滿足
2. $x\ge a_{i+1}$
$$
\vert a_i-x\vert\le\vert a_{i+1}-x\vert\\
\Rightarrow x - a_i\le x - a_{i+1}\\
\Rightarrow a_{i+1}\le a_i
$$
結果與前提矛盾，該式不成立
3. $a_i < x < a_{i + 1}$
$$
\vert a_i-x\vert\le\vert a_{i+1}-x\vert\\
\Rightarrow x-a_i\le a_{i+1}-x\\
\Rightarrow 2x\le a_i+a_{i+1}\\
\Rightarrow x\le \frac{a_i+a_{i+1}}{2}
$$
若$x\le \frac{a_i+a_{i+1}}{2}$，則此範圍滿足
3. $a_i>a_{i+1}$
$\vert a_i-x\vert\le\vert a_{i+1}-x\vert$
可以分開考慮$x$的三種範圍是否滿足關係式
1. $x\le a_{i+1}$
$$
\vert a_i-x\vert\le\vert a_{i+1}-x\vert\\
\Rightarrow a_i-x\le a_{i+1}-x\\
\Rightarrow a_i\le a_{i+1}
$$
結果與前提矛盾，該式不成立
2. $x\ge a_i$
$$
\vert a_i-x\vert\le\vert a_{i+1}-x\vert\\
\Rightarrow x - a_i\le x - a_{i+1}\\
\Rightarrow a_{i+1}\le a_i
$$
此範圍滿足
3. $a_{i+1} < x < a_i$
$$
\vert a_i-x\vert\le\vert a_{i+1}-x\vert\\
\Rightarrow a_i - x\le x - a_{i+1}\\
\Rightarrow 2x\ge a_i+a_{i+1}\\
\Rightarrow x\ge \frac{a_i+a_{i+1}}{2}
$$
若$x\ge \frac{a_i+a_{i+1}}{2}$，則此範圍滿足

所以以結論來說，若$a_i<a_{i+1}$，則$x$必須符合$x\le \frac{a_i+a_{i+1}}{2}$；若$a_i>a_{i+1}$，則$x$必須符合$x\ge \frac{a_i+a_{i+1}}{2}$；若$a_i=a_{i+1}$，則$x$無任何限制。
因為$x$為正整數，所以以上兩個條件等價於：$x\le \lfloor\frac{a_i+a_{i+1}}{2}\rfloor$、$x\ge \lceil\frac{a_i+a_{i+1}}{2}\rceil$

有了以上關係，就只要從頭到尾遍歷$a$一次，解集合即為所有相鄰兩數的$x$範圍的聯集。若集合不存在即為無解。這樣做的時間複雜度為$O{(n)}$。

### code

>> 與初見解基本上一樣，只不過我去除了一些冗句

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

#define F first
#define S second

using namespace std;

const int SIZE = 200050;
int a[SIZE];

void solve() {
    int n;
    cin >> n;
    int prev, now;
    pair<int, int> x {0, 1000000000};
    cin >> prev;
    for (int i = 1; i < n; ++i) {
        cin >> now;
        if (prev < now) {
            x.S = min(x.S, (prev + now) / 2);
        } else if (prev > now) {
            x.F = max(x.F, (prev + now + 1) / 2);
        }
        prev = now;
    }
    
    if (x.F <= x.S) {
        cout << x.F << "\n";
    } else {
        cout << "-1\n";
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

## 初見解

### 思路

>> 因為是看題解的，所以思路一樣

### code

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

#define F first
#define S second

using namespace std;

const int SIZE = 200050;
int a[SIZE];

void solve() {
    int n;
    cin >> n;
    int prev, now;
    pair<int, int> x {0, 1000000000};
    for (int i = 0; i < n; ++i) {
        if (!i) {
            cin >> prev;
            continue;
        }
        cin >> now;
        if (prev < now) {
            x.F = max(x.F, 0);
            x.S = min(x.S, (prev + now) / 2);
        } else if (prev > now) {
            x.F = max(x.F, (prev + now + 1) / 2);
            x.S = min(x.S, 1000000000);
        }
        prev = now;
    }
    
    if (x.F <= x.S) {
        cout << x.F << "\n";
    } else {
        cout << "-1\n";
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

###### tags: `每日CF梗題挑戰`