链接 : 

Problem - A - Codeforces

题意 : 

思路 : 

先判断序列是否排好序 ， 不是排好序的，直接输出0即可，排好序的 : 

先求出相邻元素之间的最小间隔，因为，要使有序非递减序列，变得不排序，肯定要找a[i]-a[i-1]最小的区域，让[1...i-1]前面的加 1  ,  后面[i....n ]部分减一，才能够得到最小的结果 ;

代码

#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(),a.end() 
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n' 
typedef long long LL ;
inline void solve(){
	int n ; cin >> n ;
	vector<int> a(n) ;
	for(int i=0;i<n;i++) cin >> a[i] ;
	bool tag = true;
	LL mi = 2e18 ;
	for(int i=1;i<n;i++){
		if(a[i]<a[i-1]){
			tag = false;
			break;
		}
		mi = min(mi , 0LL + a[i] - a[i-1] - 1); // 中间的空格数 
	}
	if(!tag){
		cout << 0 << endl;
		return ;
	}
	if(mi == -1){
		cout << 1 << endl ;
		return ; 
	}
	if(mi & 1){ // 奇数 
		cout << mi / 2 + 2 << endl;
	}else{ // 偶数 
		cout << mi / 2 + 1 << endl ;
	}
}

int main() {
	IOS
    int _ = 1;
    cin >> _;
    while(_ --) solve();
    return 0;
}