D. Absolute Sorting

D. Absolute Sorting

思路：

如果a[i] >= a[i-1]，那么我们最大可以减去(a[i] + a[i - 1]) / 2，这样减完依旧是满足a[i] >= a[i - 1]的。因此我们可以把所有满足a[i]>=a[i - 1]的答案取一个交集，即取一个最小值。

如果a[i]<a[i - 1]，那么我们最小可以减去(a[i] - a[i - 1] + 1) / 2，这样减完我们就可以使得a[i] > a[i - 1].。因此我们可以把所有满足a[i]<a[i - 1]的答案取一个交集，即取一个最大值。

最后判断这种情况是否存在即可

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 500010;

int n;
int a[N];
int dx[] = {-1, 0, 1, 0, 1, 1, -1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

int main()
{
    int T;
    cin >> T;
    while(T -- )
    {
        cin >> n;
        for (int i = 1; i <= n; i ++ )
            cin >> a[i];

        int mn = 0, mx = 0x3f3f3f3f;
        for (int i = 2; i <= n; i ++ )
        {
            if(a[i] > a[i - 1])
                mx = min(mx, a[i] + a[i - 1] >> 1);
            if(a[i] < a[i - 1])
                mn = max(mn, a[i] + a[i - 1] + 1 >> 1);
        }

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