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; }
标签:Sorting,int,mn,cin,mx,Absolute From: https://www.cnblogs.com/yctql/p/17010004.html